P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle
From MaRDI portal
(Redirected from Publication:5092409)
Recommendations
Cites work
- A complexity theory for feasible closure properties
- Complexity classes without machines: on complete languages for UP
- Complexity Measures for Public-Key Cryptosystems
- Disjoint NP-Pairs
- 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?)
- 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
(4)
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)
