Počet záznamů: 1
On the proof complexity of the Nisan-Wigderson generator based on a hard NP boolean AND coNP function
- 1.
SYSNO ASEP 0369662 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název On the proof complexity of the Nisan-Wigderson generator based on a hard NP boolean AND coNP function Tvůrce(i) Krajíček, Jan (MU-W) SAI, ORCID Zdroj.dok. Journal of Mathematical Logic. - : World Scientific Publishing - ISSN 0219-0613
Roč. 11, č. 1 (2011), s. 11-27Poč.str. 17 s. Jazyk dok. eng - angličtina Země vyd. SG - Singapur Klíč. slova proof complexity ; Nisan-Wigderson generator Vědní obor RIV BA - Obecná matematika CEP IAA100190902 GA AV ČR - Akademie věd LC505 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy CEZ AV0Z10190503 - MU-W (2005-2011) UT WOS 000294810400002 EID SCOPUS 80052754570 DOI 10.1142/S0219061311000979 Anotace 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2012
Počet záznamů: 1