Dual weak pigeonhole principle, Boolean complexity, and derandomization

0043535 - MÚ 2007 RIV NL eng J - Článek v odborném periodiku
Jeřábek, Emil
Dual weak pigeonhole principle, Boolean complexity, and derandomization.
[Duální slabé PHP, Boolevská složitost a derandomizace.]
Annals of Pure and Applied Logic. Roč. 129, č. 1 (2004), s. 1-37. ISSN 0168-0072. E-ISSN 1873-2461
Výzkumný záměr: CEZ:AV0Z1019905
Klíčová slova: bounded arithmetic * randomized algorithms * proof complexity
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 0.509, rok: 2004

We study the extension of the theory S^1_2 by the surjective weak pigeonhole principle for poly-time functions, and its connections to probabilistic algorithms, propositional proof complexity, circuit complexity, and pseudorandom generators.

Studujeme rozšíření teorie S^1_2 o surjektivní slabý princip PHP pro funkce vyčislitelné v polynomiálním čase, zvláště souvislosti této teorie s pravděpodobnostními algoritmy, složitosti výrokových důkazů, obvodovou složitost a pseudonáhodnými generátory.
Trvalý link: http://hdl.handle.net/11104/0136501