Details

Autor(en) / Beteiligte

• Arvind, Vikraman
• Köbler, Johannes
• Mundhenk, Martin
• Torán, Jacobo
• Reichel, Horst
• Tison, Sophie

Titel

Nondeterministic Instance Complexity and Hard-to-Prove Tautologies

Ist Teil von

• Lecture notes in computer science, 2000, Vol.1770, p.314-323

Ort / Verlag

Germany: Springer Berlin / Heidelberg

Erscheinungsjahr

2000

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• 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.