Reductions between disjoint NP-pairs

DOI10.1016/j.ic.2005.03.003zbMath1101.68033OpenAlexW2088113355MaRDI QIDQ2387199

Christian Glaßer, Samik Sengupta, Selman, Alan L.

Publication date: 2 September 2005

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2005.03.003

zbMATH Keywords

ReductionsDisjoint NP-pairsPromise problemsSmart reductions

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (14)

Nondeterministic functions and the existence of optimal proof systems ⋮ Classes of representable disjoint \textsf{NP}-pairs ⋮ Dimension and the structure of complexity classes ⋮ Polynomial-time axioms of choice and polynomial-time cardinality ⋮ The Shrinking Property for NP and coNP ⋮ The shrinking property for NP and coNP ⋮ The consequences of eliminating NP solutions ⋮ Tuples of disjoint \(\mathsf{NP}\)-sets ⋮ Inseparability and strong hypotheses for disjoint NP pairs ⋮ The deduction theorem for strong propositional proof systems ⋮ The Deduction Theorem for Strong Propositional Proof Systems ⋮ Unions of Disjoint NP-Complete Sets ⋮ 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
• Cook versus Karp-Levin: Separating completeness notions if NP is not small
• The complexity of optimization problems
• Complexity classes without machines: on complete languages for UP
• Promise problems complete for complexity classes
• Reductions on NP and p-selective sets
• A uniform approach to define complexity classes
• On reductions of NP sets to sparse sets
• A taxonomy of complexity classes of functions
• \(R_{1-tt}^{{\mathcal SN}}\)(NP) distinguishes robust many-one and Turing completeness
• Optimal proof systems imply complete sets for promise classes
• \(p\)-Selective sets and reducing search to decision vs. self-reducibility
• On an optimal propositional proof system and the structure of easy subsets of TAUT.
• Separation of NP-Completeness Notions
• The complexity of promise problems with applications to public-key cryptography
• Quantitative Relativizations of Complexity Classes
• Complexity Measures for Public-Key Cryptosystems
• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
• On the Shannon capacity of a graph
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• Disjoint NP-Pairs
• Tally languages and complexity classes
• Computing Solutions Uniquely Collapses the Polynomial Hierarchy

This page was built for publication: Reductions between disjoint NP-pairs