Do there exist complete sets for promise classes?
From MaRDI portal
Publication:3107337
DOI10.1002/malq.201010021zbMath1253.68138DBLPjournals/mlq/BeyersdorffS11OpenAlexW2052292580WikidataQ59902771 ScholiaQ59902771MaRDI QIDQ3107337
Zenon Sadowski, Olaf Beyersdorff
Publication date: 23 December 2011
Published in: Mathematical Logic Quarterly (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/malq.201010021
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)
Related Items (2)
Total nondeterministic Turing machines and a p-optimal proof system for SAT ⋮ Hard Instances of Algorithms and Proof Systems
Cites Work
- Unnamed Item
- Unnamed Item
- Proof systems that take advice
- Nondeterministic functions and the existence of optimal proof systems
- Canonical disjoint NP-pairs of propositional proof systems
- Classes of representable disjoint \textsf{NP}-pairs
- \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP]
- Tuples of disjoint \(\mathsf{NP}\)-sets
- A low and a high hierarchy within NP
- Complexity classes without machines: on complete languages for UP
- A taxonomy of complexity classes of functions
- Some consequences of cryptographical conjectures for \(S_2^1\) and EF
- Optimal proof systems imply complete sets for promise classes
- On an optimal propositional proof system and the structure of easy subsets of TAUT.
- Reductions between disjoint NP-pairs
- A tight Karp-Lipton collapse result in bounded arithmetic
- Propositional proof systems, the consistency of first order theories and the complexity of computations
- On Circuit-Size Complexity and the Low Hierarchy in NP
- The relative efficiency of propositional proof systems
- Disjoint NP-Pairs
- Consequences of the provability of NP ⊆ P/poly
This page was built for publication: Do there exist complete sets for promise classes?
