Number of the records: 1  

A proof complexity generator

  1. 1.
    0353760 - MÚ 2011 RIV GB eng C - Conference Paper (international conference)
    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]
    R&D Projects: GA AV ČR IAA1019401; GA MŠMT LC505
    Keywords : proof complexity * hard tatologies
    Subject RIV: BA - General Mathematics

    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.
    Permanent Link: http://hdl.handle.net/11104/0192913

     
    FileDownloadSizeCommentaryVersionAccess
    Krajicek1.pdf198.2 KBAuthor’s postprintopen-access
     
Number of the records: 1  

  This site uses cookies to make them easier to browse. Learn more about how we use cookies.