Tuples of disjoint NP-sets

DOI10.1007/S00224-007-9023-8MaRDI QIDQ929286zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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 of proofs (03F20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Tuples of Disjoint NP-Sets
• Unions of disjoint NP-complete sets
• Unions of disjoint NP-complete sets
• Disjoint NP-Pairs
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Classes of representable disjoint \textsf{NP}-pairs
• The complexity of unions of disjoint sets
• The Complexity of Unions of Disjoint Sets
• NP-Completeness, Proof Systems, and Disjoint NP-Pairs.
• scientific article; zbMATH DE number 3902038

Cites work

• Classes of representable disjoint \textsf{NP}-pairs
• Complexity Measures for Public-Key Cryptosystems
• Disjoint NP-Pairs
• Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
• scientific article; zbMATH DE number 4059391 (Why is no real title available?)
• scientific article; zbMATH DE number 819737 (Why is no real title available?)
• Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
• On reducibility and symmetry of disjoint NP pairs.
• On the Structure of Polynomial Time Reducibility
• Optimal proof systems imply complete sets for promise classes
• 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

(7)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q929286)