Do there exist complete sets for promise classes?

DOI10.1002/MALQ.201010021zbMATH Open1253.68138DBLPjournals/mlq/BeyersdorffS11OpenAlexW2052292580WikidataQ59902771 ScholiaQ59902771MaRDI QIDQ3107337FDOQ3107337

Authors: Olaf Beyersdorff, Zenon Sadowski 

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

Recommendations

• Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes
• scientific article; zbMATH DE number 1335888
• Optimal proof systems imply complete sets for promise classes
• scientific article; zbMATH DE number 1136087
• Promise problems complete for complexity classes

zbMATH Keywords

computational complexityoptimal proof systemspromise classes

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Cites Work

• A taxonomy of complexity classes of functions
• Complexity classes without machines: on complete languages for UP
• Some consequences of cryptographical conjectures for \(S_2^1\) and EF
• Title not available (Why is that?)
• The relative efficiency of propositional proof systems
• A low and a high hierarchy within NP
• Title not available (Why is that?)
• Disjoint NP-Pairs
• Canonical disjoint NP-pairs of propositional proof systems
• \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP
• Optimal proof systems imply complete sets for promise classes
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• Consequences of the provability of NP ⊆ P/poly
• Reductions between disjoint NP-pairs
• A tight Karp-Lipton collapse result in bounded arithmetic
• Proof systems that take advice
• On Circuit-Size Complexity and the Low Hierarchy in NP
• On an optimal propositional proof system and the structure of easy subsets of TAUT.
• Nondeterministic functions and the existence of optimal proof systems
• Classes of representable disjoint \textsf{NP}-pairs
• Tuples of disjoint \(\mathsf{NP}\)-sets

Cited In (7)

• Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes
• Proof systems that take advice
• Total nondeterministic Turing machines and a p-optimal proof system for SAT
• Hard Instances of Algorithms and Proof Systems
• Promise problems complete for complexity classes
• Optimal proof systems imply complete sets for promise classes
• Real benefit of promises and advice

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)