Do there exist complete sets for promise classes?
From MaRDI portal
Publication:3107337
Recommendations
Cites work
- scientific article; zbMATH DE number 192916 (Why is no real title available?)
- scientific article; zbMATH DE number 477971 (Why is no real title available?)
- A low and a high hierarchy within NP
- A taxonomy of complexity classes of functions
- A tight Karp-Lipton collapse result in bounded arithmetic
- Canonical disjoint NP-pairs of propositional proof systems
- Classes of representable disjoint \textsf{NP}-pairs
- Complexity classes without machines: on complete languages for UP
- Consequences of the provability of NP ⊆ P/poly
- Disjoint NP-Pairs
- Nondeterministic functions and the existence of optimal proof systems
- On Circuit-Size Complexity and the Low Hierarchy in NP
- On an optimal propositional proof system and the structure of easy subsets of TAUT.
- Optimal proof systems imply complete sets for promise classes
- Proof systems that take advice
- Propositional proof systems, the consistency of first order theories and the complexity of computations
- Reductions between disjoint NP-pairs
- Some consequences of cryptographical conjectures for \(S_2^1\) and EF
- The relative efficiency of propositional proof systems
- Tuples of disjoint \(\mathsf{NP}\)-sets
- \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP
Cited in
(7)- Optimal proof systems imply complete sets for promise classes
- Promise problems complete for complexity classes
- Hard Instances of Algorithms and Proof Systems
- Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes
- Proof systems that take advice
- Real benefit of promises and advice
- Total nondeterministic Turing machines and a p-optimal proof system for SAT
This page was built for publication: Do there exist complete sets for promise classes?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3107337)
