Classes of representable disjoint \textsf{NP}-pairs
From MaRDI portal
Publication:884465
DOI10.1016/j.tcs.2007.02.005zbMath1118.68069OpenAlexW2134646730WikidataQ57950018 ScholiaQ57950018MaRDI QIDQ884465
Publication date: 6 June 2007
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2007.02.005
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)
Related Items (10)
Nondeterministic functions and the existence of optimal proof systems ⋮ Logical Closure Properties of Propositional Proof Systems ⋮ Proof system representations of degrees of disjoint NP-pairs ⋮ Tuples of disjoint \(\mathsf{NP}\)-sets ⋮ Total nondeterministic Turing machines and a p-optimal proof system for SAT ⋮ The deduction theorem for strong propositional proof systems ⋮ The Deduction Theorem for Strong Propositional Proof Systems ⋮ On the correspondence between arithmetic theories and propositional proof systems – a survey ⋮ Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes ⋮ Do there exist complete sets for promise classes?
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Oracles for structural properties: The isomorphism problem and public-key cryptography
- Some consequences of cryptographical conjectures for \(S_2^1\) and EF
- Optimal proof systems imply complete sets for promise classes
- On reducibility and symmetry of disjoint NP pairs.
- Non-automatizability of bounded-depth Frege proofs
- Reductions between disjoint NP-pairs
- Propositional proof systems, the consistency of first order theories and the complexity of computations
- Quantified propositional calculi and fragments of bounded arithmetic
- Complexity Measures for Public-Key Cryptosystems
- On the Shannon capacity of a graph
- The relative efficiency of propositional proof systems
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Lower bounds for cutting planes proofs with small coefficients
- Lower bounds for resolution and cutting plane proofs and monotone computations
- On Interpolation and Automatization for Frege Systems
- Disjoint NP-Pairs
- Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
- Mathematical Foundations of Computer Science 2005
This page was built for publication: Classes of representable disjoint \textsf{NP}-pairs
