Classes of representable disjoint \textsf{NP}-pairs
From MaRDI portal
Publication:884465
Recommendations
Cites work
- scientific article; zbMATH DE number 1948187 (Why is no real title available?)
- scientific article; zbMATH DE number 819737 (Why is no real title available?)
- scientific article; zbMATH DE number 1390276 (Why is no real title available?)
- Complexity Measures for Public-Key Cryptosystems
- Disjoint NP-Pairs
- Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
- 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
- Mathematical Foundations of Computer Science 2005
- Non-automatizability of bounded-depth Frege proofs
- On Interpolation and Automatization for Frege Systems
- On reducibility and symmetry of disjoint NP pairs.
- On the Shannon capacity of a graph
- Optimal proof systems imply complete sets for promise classes
- Oracles for structural properties: The isomorphism problem and public-key cryptography
- Propositional proof systems, the consistency of first order theories and the complexity of computations
- Quantified propositional calculi and fragments of bounded arithmetic
- Reductions between disjoint NP-pairs
- Some consequences of cryptographical conjectures for \(S_2^1\) and EF
- The relative efficiency of propositional proof systems
Cited in
(14)- Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes
- The Deduction Theorem for Strong Propositional Proof Systems
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
- Nondeterministic functions and the existence of optimal proof systems
- 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
- Disjoint NP-pairs and propositional proof systems
- Proof system representations of degrees of disjoint NP-pairs
- Do there exist complete sets for promise classes?
- Disjoint NP-Pairs
- On the correspondence between arithmetic theories and propositional proof systems – a survey
- Logical Closure Properties of Propositional Proof Systems
- Canonical disjoint NP-pairs of propositional proof systems
This page was built for publication: Classes of representable disjoint \textsf{NP}-pairs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q884465)
