Strukturovaný PHP, vyhledávací problémy a obtížné tautologie

Kód výsledku v IS VaVaI

RIV/67985840:_____/05:00022098 - isvavai.cz

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Structured pigeonhole principle, search problems and hard tautologies

Popis výsledku v původním jazyce

We consider exponentially large finite relational structures whose basic relations are computed by polynomial size circuits. We study behaviour of such structures when pulled back by (nonuniform) polynomial-time maps to a bigger or to a smaller universe.This is applied to proof complexity and to complexity of search problems.

Název v anglickém jazyce

Structured pigeonhole principle, search problems and hard tautologies

Popis výsledku anglicky

We consider exponentially large finite relational structures whose basic relations are computed by polynomial size circuits. We study behaviour of such structures when pulled back by (nonuniform) polynomial-time maps to a bigger or to a smaller universe.This is applied to proof complexity and to complexity of search problems.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2005

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Journal of Symbolic Logic

ISSN

0022-4812

e-ISSN

—

Svazek periodika

70

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

12

Strana od-do

619-630

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—