P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle

DOI10.4230/LIPIcs.MFCS.2019.47OpenAlexW3213397036MaRDI QIDQ5092409

Titus Dose

Publication date: 21 July 2022

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/10991/pdf/LIPIcs-MFCS-2019-47.pdf

zbMATH Keywords

NP-completeproof systemsoracleupdisjoint NP-pair

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• 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
• A complexity theory for feasible closure properties
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• Complexity Measures for Public-Key Cryptosystems
• The relative efficiency of propositional proof systems
• INCOMPLETENESS IN THE FINITE DOMAIN
• Disjoint NP-Pairs
• Logical Foundations of Mathematics and Computational Complexity
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle