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

DOI10.4230/LIPICS.MFCS.2019.47OpenAlexW3213397036MaRDI QIDQ5092409FDOQ5092409

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

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

zbMATH Keywords

NP-completeoracleproof systemsupdisjoint NP-pair

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Title not available (Why is that?)
• Complexity classes without machines: on complete languages for UP
• The relative efficiency of propositional proof systems
• Complexity Measures for Public-Key Cryptosystems
• Disjoint NP-Pairs
• Title not available (Why is that?)
• Optimal proof systems imply complete sets for promise classes
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• Title not available (Why is that?)
• A complexity theory for feasible closure properties
• Logical foundations of mathematics and computational complexity. A gentle introduction
• Incompleteness in the finite domain
• Nondeterministic functions and the existence of optimal 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)