Nondeterministic instance complexity and hard-to-prove tautologies
Nondeterministic instance complexity and hard-to-prove tautologies
Vikraman Arvind, Johannes Köbler, Martin Mundhenk and Jacobo
Torán
Abstract:
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.
Ps-File: Nondeterministic instance complexity and hard-to-prove tautologies
zuletzt geändert:
31.10.05
SK
Document Actions
Persönliche Werkzeuge
- Sie sind nicht eingeloggt.
- Log in
Deutsch
English