Unions of Disjoint NP-Complete Sets

DOI10.1145/2591508zbMath1320.68091OpenAlexW2045093350MaRDI QIDQ5892145

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

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

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

Cites Work

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

This page was built for publication: Unions of Disjoint NP-Complete Sets