Počet záznamů: 1
A proof complexity generator
- 1.0353760 - MÚ 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ŠMT 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 souboru Staženo Velikost Komentář Verze Přístup Krajicek1.pdf 1 98.2 KB Autorský postprint povolen
Počet záznamů: 1