An oracle exists relative to which TAUT has neither optimal proof systems nor recursive jump operators (even with infinite PH), showing Khaniki's question is not relativizably provable.
Learning Algorithms Versus Automatability of Frege Systems , booktitle =
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
fields
cs.CC 2verdicts
UNVERDICTED 2representative citing papers
Short Resolution refutations of Ref(φ) yield satisfying assignments for φ in polynomial time via a PV1-formalizable construction, and the Proof Analysis Problem is NP-complete for Extended Frege.
citing papers explorer
-
Recursive Jump Operators and Optimal Proof Systems
An oracle exists relative to which TAUT has neither optimal proof systems nor recursive jump operators (even with infinite PH), showing Khaniki's question is not relativizably provable.
-
The Proof Analysis Problem
Short Resolution refutations of Ref(φ) yield satisfying assignments for φ in polynomial time via a PV1-formalizable construction, and the Proof Analysis Problem is NP-complete for Extended Frege.