On the proof complexity of the Nisan-Wigderson generator based on a hard NP boolean AND coNP function

0369662 - MÚ 2012 RIV SG eng J - Článek v odborném periodiku
Krajíček, Jan
On the proof complexity of the Nisan-Wigderson generator based on a hard NP boolean AND coNP function.
Journal of Mathematical Logic. Roč. 11, č. 1 (2011), s. 11-27. ISSN 0219-0613. E-ISSN 1793-6691
Grant CEP: GA AV ČR IAA100190902; GA MŠMT LC505
Výzkumný záměr: CEZ:AV0Z10190503
Klíčová slova: proof complexity * Nisan-Wigderson generator
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 0.500, rok: 2011
http://www.worldscinet.com/jml/11/1101/S0219061311000979.html

We prove the consistency of a statement generalizing Razborov's conjecture from proof complexity with the true universal theory in the language of Cook's theory PV.
Trvalý link: http://hdl.handle.net/11104/0203675