Power indices and easier hard problems

DOI10.1007/BF02090776zbMath0719.68025OpenAlexW2042654457MaRDI QIDQ5751941

Richard E. Stearns, Harry B. III Hunt

Publication date: 1990

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02090776

zbMATH Keywords

NP-complete problemsplanaritypower indexCLIQUESATseparator

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (10)

Efficient algorithms for solving systems of linear equations and path problems ⋮ Complement, Complexity, and Symmetric Representation ⋮ New methods for 3-SAT decision and worst-case analysis ⋮ Predecessor existence problems for finite discrete dynamical systems ⋮ On quasilinear-time complexity theory ⋮ The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness ⋮ Refining complexity analyses in planning by exploiting the exponential time hypothesis ⋮ Power indices and easier hard problems ⋮ Sorting, linear time and the satisfiability problem ⋮ Which problems have strongly exponential complexity?

Uses Software

• PARTITION

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Short propositional formulas represent nondeterministic computations
• An application of the planar separator theorem to counting problems
• The Euclidean traveling salesman problem is NP-complete
• The Complexity of Very Simple Boolean Formulas with Applications
• Graph minors. II. Algorithmic aspects of tree-width
• Applications of a Planar Separator Theorem
• Linear time transformations between combinatorial problems
• Dynamic Programming is Optimal for Nonserial Optimization Problems
• Satisfiability Is Quasilinear Complete in NQL
• Nonlinear Algebra and Optimization on Rings are “Hard”
• The complexity of satisfiability problems
• The complexity of theorem-proving procedures
• Power indices and easier hard problems

This page was built for publication: Power indices and easier hard problems