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 - Journal Article
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
R&D Projects: GA AV ČR IAA100190902; GA MŠMT LC505
Institutional research plan: CEZ:AV0Z10190503
Keywords : proof complexity * Nisan-Wigderson generator
Subject RIV: BA - General Mathematics
Impact factor: 0.500, year: 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.
Permanent Link: http://hdl.handle.net/11104/0203675