The complexity of unions of disjoint sets

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

zbMATH Keywords

structural complexitymitotic setNP-hard setp-selective set

Mathematics Subject Classification ID

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