Počet záznamů: 1

A proof complexity generator

  1. 1.
    0353760 - MU-W 2011 RIV GB eng C - Konferenční příspěvek (zahraniční konf.)
    Krajíček, Jan
    A proof complexity generator.
    Logic, Methodology and Philosophy of Science. London: College Publications, 2009 - (Glymour, C.; Wang, W.; Westerstahl, D.), s. 185-190. ISBN 978-1-904987-45-1.
    [International Congress in Logic, Methodology and Philosophy of Science /13./. Beijing (CN), 09.08.2007-15.08.2007]
    Grant CEP: GA AV ČR IAA1019401; GA MŠk LC505
    Klíčová slova: proof complexity * hard tatologies
    Kód oboru RIV: BA - Obecná matematika

    We define by a 2DNF formula a Boolean map from n bits to n+1 bits such that in any propositional proof system for which the PHP principle is hard, it is hard to prove about any n+1 string that it is outside of the range of the map.
    Trvalý link: http://hdl.handle.net/11104/0192913
    Název souboruStaženoVelikostKomentářVerzePřístup
    Krajicek1.pdf198.2 KBAutorský postprintpovolen