Tuples of disjoint \(\mathsf{NP}\)-sets

DOI10.1007/S00224-007-9023-8zbMath1148.68021DBLPjournals/mst/Beyersdorff08OpenAlexW1999473833WikidataQ59903789 ScholiaQ59903789MaRDI QIDQ929286

Olaf Beyersdorff

Publication date: 17 June 2008

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-007-9023-8

zbMATH Keywords

Propositional proof systems

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Related Items (4)

Nondeterministic functions and the existence of optimal proof systems ⋮ Total nondeterministic Turing machines and a p-optimal proof system for SAT ⋮ The deduction theorem for strong propositional proof systems ⋮ Do there exist complete sets for promise classes?

Cites Work

• Unnamed Item
• Unnamed Item
• Classes of representable disjoint \textsf{NP}-pairs
• 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.
• 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 Structure of Polynomial Time Reducibility
• The relative efficiency of propositional proof systems
• Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
• Disjoint NP-Pairs
• Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds

This page was built for publication: Tuples of disjoint \(\mathsf{NP}\)-sets