Complexity of partial satisfaction. II.

DOI10.4171/EM/202zbMath1283.68165OpenAlexW2070114427WikidataQ106019114 ScholiaQ106019114MaRDI QIDQ452481

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

complexityNP-completehardnessmaximum satisfiability problem

Mathematics Subject Classification ID

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

Related Items (5)

Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey ⋮ Partial Satisfaction of k-Satisfiable Formulas ⋮ A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications ⋮ A New Bound for 3-Satisfiable Maxsat and Its Algorithmic Application ⋮ Locally consistent constraint satisfaction problems

Cites Work

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

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