Name
Abstract | ||
|---|---|---|
In this note we first formalize the notion of hard tautologies using a nondeterministic generalization of instance complexity. We then show, under reasonable complexity-theoretic assumptions, that there are infinitely many propositional tautologies that are hard to prove in any sound propositional proof system. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1007/3-540-46541-3_26 | STACS |
Keywords | Field | DocType |
hard tautology,nondeterministic instance complexity,reasonable complexity-theoretic assumption,sound propositional proof system,instance complexity,hard-to-prove tautologies,nondeterministic generalization,propositional tautology | Discrete mathematics,Tautology (logic),Kolmogorov complexity,Nondeterministic algorithm,Universal Turing machine,Computer science,Propositional calculus,Propositional proof system | Conference |
Volume | ISSN | ISBN |
1770 | 0302-9743 | 3-540-67141-2 |
Citations | PageRank | References |
2 | 0.42 | 10 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vikraman Arvind | 1 | 296 | 38.18 |
| Johannes Köbler | 2 | 580 | 46.51 |
| Martin Mundhenk | 3 | 11 | 1.86 |
| Jacobo Torán | 4 | 564 | 49.26 |