Complexity of partial satisfaction. II.

DOI10.4171/EM/202MaRDI QIDQ452481zbMATH OpenOpenAlexWikidataFDO

Authors Karl J. Lieberherr, Ernst Specker

Publication date 21 September 2012

Published in Elemente der Mathematik (Search for Journal in Brave)

Full work available at URL https://doi.org/10.4171/em/202

zbMATH Keywords

complexityhardnessmaximum satisfiability problemNP-complete

Mathematics Subject Classification ID

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

Recommendations

• A simplified NP-complete satisfiability problem
• The complexity of satisfiability problems
• A dichotomy theorem for maximum generalized satisfiability problems.
• A simplified NP-complete MAXSAT problem
• A Complexity Index for Satisfiability Problems

Cites work

• Algorithmic extremal problems in combinatorial optimization
• Complexity of Partial Satisfaction
• On Local Versus Global Satisfiability
• The complexity of satisfiability problems

Cited in

(6)

• On the complexity of the maximum satisfiability problem for Horn formulas
• The complexity of selecting maximal solutions
• Locally consistent constraint satisfaction problems
• Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
• A new bound for 3-satisfiable MaxSat and its algorithmic application
• Partial Satisfaction of k-Satisfiable Formulas

This page was built for publication: Complexity of partial satisfaction. II.

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