An oracle separating conjectures about incompleteness in the finite domain

DOI10.1016/J.TCS.2020.01.003zbMath1436.68124OpenAlexW3000303691WikidataQ123208248 ScholiaQ123208248MaRDI QIDQ2290649

Titus Dose

Publication date: 29 January 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2020.01.003

zbMATH Keywords

proof systemsoracledisjoint NP-pairsUPP-optimal

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Related Items (2)

NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN ⋮ Further oracles separating conjectures about incompleteness in the finite domain

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On total functions, existence theorems and computational complexity
• Nondeterministic functions and the existence of optimal proof systems
• Complexity classes without machines: on complete languages for UP
• Optimal proof systems imply complete sets for promise classes
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• The complexity of promise problems with applications to public-key cryptography
• Complexity Measures for Public-Key Cryptosystems
• Cryptocomplexity and NP-completeness
• The relative efficiency of propositional proof systems
• INCOMPLETENESS IN THE FINITE DOMAIN
• Disjoint NP-Pairs
• Logical Foundations of Mathematics and Computational Complexity
• NP-Completeness, Proof Systems, and Disjoint NP-Pairs.

This page was built for publication: An oracle separating conjectures about incompleteness in the finite domain