Classes of representable disjoint \textsf{NP}-pairs

DOI10.1016/j.tcs.2007.02.005zbMath1118.68069OpenAlexW2134646730WikidataQ57950018 ScholiaQ57950018MaRDI QIDQ884465

Olaf Beyersdorff

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

zbMATH Keywords

propositional proof systemsdisjoint NP-pairs

Mathematics Subject Classification ID

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