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

DOI10.4230/LIPICS.MFCS.2019.47MaRDI QIDQ5092409zbMATH OpenOpenAlexFDO

Authors 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-completeoracleproof systemsupdisjoint NP-pair

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• An oracle separating conjectures about incompleteness in the finite domain
• Disjoint NP-Pairs
• Further oracles separating conjectures about incompleteness in the finite domain
• Disjoint NP-pairs and propositional proof systems
• Mathematical Foundations of Computer Science 2005

Cites work

• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 2080216 (Why is no real title available?)
• scientific article; zbMATH DE number 910749 (Why is no real title available?)
• A complexity theory for feasible closure properties
• Complexity Measures for Public-Key Cryptosystems
• Complexity classes without machines: on complete languages for UP
• Disjoint NP-Pairs
• Incompleteness in the finite domain
• Logical foundations of mathematics and computational complexity. A gentle introduction
• Nondeterministic functions and the existence of optimal proof systems
• Optimal proof systems imply complete sets for promise classes
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• The relative efficiency of propositional proof systems

Cited in

(2)

• Theory and Applications of Models of Computation
• Mathematical Foundations of Computer Science 2005

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5092409)