Optimal proof systems imply complete sets for promise classes
From MaRDI portal
Recommendations
Cites work
- A uniform approach to define complexity classes
- Complexity classes without machines: on complete languages for UP
- scientific article; zbMATH DE number 3896918 (Why is no real title available?)
- scientific article; zbMATH DE number 4004177 (Why is no real title available?)
- scientific article; zbMATH DE number 46423 (Why is no real title available?)
- scientific article; zbMATH DE number 192916 (Why is no real title available?)
- scientific article; zbMATH DE number 3583767 (Why is no real title available?)
- scientific article; zbMATH DE number 1335888 (Why is no real title available?)
- scientific article; zbMATH DE number 1136087 (Why is no real title available?)
- scientific article; zbMATH DE number 1500532 (Why is no real title available?)
- scientific article; zbMATH DE number 761756 (Why is no real title available?)
- scientific article; zbMATH DE number 819737 (Why is no real title available?)
- On an optimal quantified propositional proof system nal proof system and a complete language for NP ∩ co-NP for NP ∩ co-NP
- On Approximation Algorithms for # P
- On the power of parity polynomial time
- Propositional proof systems, the consistency of first order theories and the complexity of computations
- RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS
- Sparse sets in NP-P: EXPTIME versus NEXPTIME
- Tally languages and complexity classes
- The Complexity of Propositional Proofs
- The relative efficiency of propositional proof systems
- Universal classes of hash functions
Cited in
(32)- Promise problems complete for complexity classes
- Total nondeterministic Turing machines and a p-optimal proof system for SAT
- Further oracles separating conjectures about incompleteness in the finite domain
- An oracle separating conjectures about incompleteness in the finite domain
- Reductions between disjoint NP-pairs
- A Parameterized Halting Problem
- Do there exist complete sets for promise classes?
- Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes
- Logical Closure Properties of Propositional Proof Systems
- The Shrinking Property for NP and coNP
- On the correspondence between arithmetic theories and propositional proof systems – a survey
- THE INFORMATIONAL CONTENT OF CANONICAL DISJOINT NP-PAIRS
- Does Advice Help to Prove Propositional Tautologies?
- Towards NP-P via proof complexity and search
- scientific article; zbMATH DE number 1335888 (Why is no real title available?)
- scientific article; zbMATH DE number 1136087 (Why is no real title available?)
- scientific article; zbMATH DE number 1500532 (Why is no real title available?)
- Incompleteness in the finite domain
- scientific article; zbMATH DE number 1929970 (Why is no real title available?)
- P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle
- scientific article; zbMATH DE number 5201477 (Why is no real title available?)
- The Complexity of Propositional Proofs
- The Deduction Theorem for Strong Propositional Proof Systems
- Proof systems that take advice
- Hard instances of algorithms and proof systems
- The shrinking property for NP and coNP
- On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography
- An oracle with no up-complete sets, but NP = PSPACE
- Nondeterministic functions and the existence of optimal proof systems
- Classes of representable disjoint \textsf{NP}-pairs
- Tuples of disjoint \(\mathsf{NP}\)-sets
- The deduction theorem for strong propositional proof systems
This page was built for publication: Optimal proof systems imply complete sets for promise classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1398371)
