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.
On Optimal Algorithms and Optimal Proof Systems , year =
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
fields
cs.CC 1years
2026 1verdicts
UNVERDICTED 1representative citing papers
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.