The complexity of unions of disjoint sets
From MaRDI portal
Publication:955349
DOI10.1016/j.jcss.2008.05.001zbMath1152.68019OpenAlexW2073363580MaRDI QIDQ955349
Klaus W. Wagner, Christian Glaßer, Stephen Travers, Selman, Alan L.
Publication date: 19 November 2008
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2008.05.001
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (3)
Polynomial-time axioms of choice and polynomial-time cardinality ⋮ Unions of Disjoint NP-Complete Sets ⋮ Constructing NP-intermediate problems by blowing holes with parameters of various properties
Cites Work
- A low and a high hierarchy within NP
- A comparison of polynomial time reducibilities
- Relative complexity of checking and evaluating
- Separability and one-way functions
- Uniformly hard languages.
- On the unique satisfiability problem
- Comparing Reductions to NP-Complete Sets
- The difference and truth-table hierarchies for NP
- Complexity Measures for Public-Key Cryptosystems
- Natural Self-Reducible Sets
- The Boolean Hierarchy I: Structural Properties
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Inclusion complete tally languages and the Hartmanis-Berman conjecture
- On the Shannon capacity of a graph
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- Splittings, Robustness, and Structure of Complete Sets
- Redundancy in Complete Sets
- Machines that Can Output Empty Words
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: The complexity of unions of disjoint sets
