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)

Review text

Summary: What is easy and when does it become hard to find a solution of a problem? We give a sharp answer to this question for various generalizations of the well-known maximum satisfiability problem. For several maximum \(\psi\)-satisfiability problems we explicitly determine algebraic numbers \(\tau_{\psi}\), \(0<\tau_{\psi} < 1\), which separate NP-complete from polynomial problems. The fraction \(\tau_{\psi}\) of the clauses of a \(\psi\)-formula can be satisfied in polynomial time, while the set of \(\psi\)-formulas which have an assignment satisfying the fraction \(\tau'\), where \(\tau' > \tau_{\psi}\) and \(\tau'\) is rational, of the clauses is NP-complete. For Part I see [the authors, J. Assoc. Comput. Mach. 28, 411--421 (1981; Zbl 0456.68078)].

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)