Počet záznamů: 1
A proof complexity generator
- 1.
SYSNO ASEP 0353760 Druh ASEP C - Konferenční příspěvek (mezinárodní konf.) Zařazení RIV D - Článek ve sborníku Název A proof complexity generator Tvůrce(i) Krajíček, Jan (MU-W) SAI, ORCID Zdroj.dok. Logic, Methodology and Philosophy of Science. - London : College Publications, 2009 / Glymour C. ; Wang W. ; Westerstahl D. - ISBN 978-1-904987-45-1 Rozsah stran s. 185-190 Poč.str. 6 s. Akce International Congress in Logic, Methodology and Philosophy of Science /13./ Datum konání 09.08.2007-15.08.2007 Místo konání Beijing Země CN - Čína Typ akce WRD Jazyk dok. eng - angličtina Země vyd. GB - Velká Británie Klíč. slova proof complexity ; hard tatologies Vědní obor RIV BA - Obecná matematika CEP IAA1019401 GA AV ČR - Akademie věd LC505 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy Anotace 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2011
Počet záznamů: 1