Unions of disjoint NP-complete sets

DOI10.1145/2591508MaRDI QIDQ5892145zbMATH OpenOpenAlexWikidataFDO

Authors Christian Glaßer, John M. Hitchcock, Aduri Pavan, Stephan Travers

Publication date 7 September 2015

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2591508

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• Unions of disjoint NP-complete sets
• The complexity of unions of disjoint sets
• The Complexity of Unions of Disjoint Sets
• Disjoint NP-Pairs
• Reductions between disjoint NP-pairs

Cites work

• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Canonical disjoint NP-pairs of propositional proof systems
• Circuit lower bounds for Merlin-Arthur classes
• Complexity Measures for Public-Key Cryptosystems
• Easiness assumptions and hardness tests: Trading time for zero error
• Inseparability and strong hypotheses for disjoint NP pairs
• Natural Self-Reducible Sets
• On Isomorphisms and Density of NP and Other Complete Sets
• Properties of NP‐Complete Sets
• Randomness vs time: Derandomization under a uniform assumption
• Reductions between disjoint NP-pairs
• Splitting NP-Complete Sets
• The complexity of promise problems with applications to public-key cryptography
• The complexity of unions of disjoint sets

Cited in

(9)

• Union-freeness, deterministic union-freeness and union-complexity
• The Complexity of Unions of Disjoint Sets
• scientific article; zbMATH DE number 4049047 (Why is no real title available?)
• scientific article; zbMATH DE number 4128862 (Why is no real title available?)
• scientific article; zbMATH DE number 1204008 (Why is no real title available?)
• Unions of disjoint NP-complete sets
• Tuples of disjoint \(\mathsf{NP}\)-sets
• Disjoint unions of complete minors
• The complexity of unions of disjoint sets

This page was built for publication: Unions of disjoint NP-complete sets

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