Power indices and easier hard problems

DOI10.1007/BF02090776MaRDI QIDQ5751941zbMATH OpenOpenAlexFDO

Authors R. E. Stearns, H. 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

CLIQUENP-complete problemsplanaritypower indexSATseparator

Mathematics Subject Classification ID

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

Recommendations

• A simplified NP-complete satisfiability problem
• A Complexity Index for Satisfiability Problems
• scientific article; zbMATH DE number 152108
• The complexity of satisfiability problems
• Satisfiability with index dependency

Cites work

• An application of the planar separator theorem to counting problems
• Applications of a Planar Separator Theorem
• Dynamic Programming is Optimal for Nonserial Optimization Problems
• Graph minors. II. Algorithmic aspects of tree-width
• scientific article; zbMATH DE number 4037175 (Why is no real title available?)
• scientific article; zbMATH DE number 4081531 (Why is no real title available?)
• scientific article; zbMATH DE number 3711409 (Why is no real title available?)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Linear time transformations between combinatorial problems
• Nonlinear Algebra and Optimization on Rings are “Hard”
• Power indices and easier hard problems
• Satisfiability Is Quasilinear Complete in NQL
• Short propositional formulas represent nondeterministic computations
• The complexity of satisfiability problems
• The complexity of theorem-proving procedures
• The Complexity of Very Simple Boolean Formulas with Applications
• The Euclidean traveling salesman problem is NP-complete

Cited in

(11)

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

Describes a project that uses

Uses Software

• PARTITION

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

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