On reducibility and symmetry of disjoint NP pairs.

DOI10.1016/S0304-3975(02)00411-5zbMath1045.68058MaRDI QIDQ1401249

Pavel Pudlák

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Cutting planesResolutionPropositional proof systemsDisjoint NP-pairsPolynomial reducibility

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25)

Related Items (19)

On the automatizability of resolution and related propositional proof systems ⋮ Nondeterministic functions and the existence of optimal proof systems ⋮ Canonical disjoint NP-pairs of propositional proof systems ⋮ Classes of representable disjoint \textsf{NP}-pairs ⋮ Unnamed Item ⋮ Logical Closure Properties of Propositional Proof Systems ⋮ Parity Games and Propositional Proofs ⋮ Proof system representations of degrees of disjoint NP-pairs ⋮ On the automatizability of polynomial calculus ⋮ The canonical pairs of bounded depth Frege systems ⋮ Tuples of disjoint \(\mathsf{NP}\)-sets ⋮ Finding the Hardest Formulas for Resolution ⋮ On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography ⋮ Mean-payoff games and propositional proofs ⋮ The deduction theorem for strong propositional proof systems ⋮ Unnamed Item ⋮ The Deduction Theorem for Strong Propositional Proof Systems ⋮ THE INFORMATIONAL CONTENT OF CANONICAL DISJOINT NP-PAIRS ⋮ On the proof complexity of logics of bounded branching

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An exponential lower bound for the size of monotone real circuits
• Some consequences of cryptographical conjectures for \(S_2^1\) and EF
• Superpolynomial lower bounds for monotone span programs
• Resolution Is Not Automatizable Unless W[P Is Tractable]
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• Complexity Measures for Public-Key Cryptosystems
• On the Shannon capacity of a graph
• The relative efficiency of propositional proof systems
• On Interpolation and Automatization for Frege Systems

This page was built for publication: On reducibility and symmetry of disjoint NP pairs.