Number of the records: 1

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

SYSNO ASEP	0369662
Document Type	J - Journal Article
R&D Document Type	Journal Article
Subsidiary J	Článek ve WOS
Title	On the proof complexity of the Nisan-Wigderson generator based on a hard NP boolean AND coNP function
Author(s)	Krajíček, Jan (MU-W)_{SAI, ORCID}
Source Title	Journal of Mathematical Logic. - : World Scientific Publishing - ISSN 0219-0613 Roč. 11, č. 1 (2011), s. 11-27
Number of pages	17 s.
Language	eng - English
Country	SG - Singapore
Keywords	proof complexity ; Nisan-Wigderson generator
Subject RIV	BA - General Mathematics
R&D Projects	IAA100190902 GA AV ČR - Academy of Sciences of the Czech Republic (AV ČR)
	LC505 GA MŠMT - Ministry of Education, Youth and Sports (MEYS)
CEZ	AV0Z10190503 - MU-W (2005-2011)
UT WOS	000294810400002
EID SCOPUS	80052754570
DOI	10.1142/S0219061311000979
Annotation	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.
Workplace	Mathematical Institute
Contact	Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757
Year of Publishing	2012

Number of the records: 1