Počet záznamů: 1

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

  1. 1.
    0369662 - MU-W 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
    Grant CEP: GA AV ČR IAA100190902; GA MŠk 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
    Název souboruStaženoVelikostKomentářVerzePřístup
    Krajicek1.pdf3436.2 KBVydavatelský postprintvyžádat