Max-SAT

E537213
Boolean optimization problem computational problem constraint optimization problem optimization problem

Max-SAT is the optimization variant of the Boolean satisfiability problem in which the goal is to find an assignment that satisfies the maximum possible number of clauses, making it a central problem in approximation algorithms and complexity theory.

Jump to: Surface forms Statements Referenced by

Observed surface forms (1)

Surface form Occurrences
MaxSMT 1

Statements (48)

Predicate Object
instanceOf Boolean optimization problem ⓘ
computational problem ⓘ
constraint optimization problem ⓘ
optimization problem ⓘ
alternativeGoal minimize number of unsatisfied clauses ⓘ
approximability admits constant-factor approximation algorithms ⓘ
admits polynomial-time approximation schemes for some restricted cases ⓘ
basedOn Boolean satisfiability problem ⓘ
belongsTo computational complexity theory NERFINISHED ⓘ
theory of approximation algorithms ⓘ
decisionVersion asks if there exists an assignment satisfying at least K clauses ⓘ
decisionVersionComplexity NP-complete ⓘ
definedOver Boolean variables ⓘ
clauses in conjunctive normal form ⓘ
generalizes SAT ⓘ
goal maximize number of satisfied clauses ⓘ
hasBenchmarkInstances Max-SAT Evaluation competitions ⓘ
hasRandomizedApproximation true ⓘ
hasVariant k-Max-SAT NERFINISHED ⓘ
partial Max-SAT ⓘ
weighted Max-SAT ⓘ
weighted partial Max-SAT ⓘ
input CNF formula ⓘ
isCentralProblemIn approximation algorithms ⓘ
automated reasoning ⓘ
constraint programming ⓘ
proof complexity ⓘ
isGeneralizationOf maximum satisfiable subset problem ⓘ
isMaximizationProblem true ⓘ
isNPComplete false ⓘ
isNPHard true ⓘ
output maximum number of satisfiable clauses ⓘ
truth assignment to variables ⓘ
relatedProblem Max-CSP ⓘ
Max-CUT ⓘ
Min-SAT ⓘ
restrictionOf Max-k-SAT when clause size is bounded by k ⓘ
solvedBy SAT-based Max-SAT solvers ⓘ
branch-and-bound algorithms ⓘ
integer linear programming formulations ⓘ
local search algorithms ⓘ
usedIn bioinformatics ⓘ
configuration problems ⓘ
hardware verification ⓘ
planning ⓘ
preference reasoning ⓘ
scheduling ⓘ
software verification ⓘ

Referenced by (2)

Full triples — surface form annotated when it differs from this entity's canonical label.

“Inapproximability results for SAT and other problems” → relatedConcept → Max-SAT ⓘ
subject surface form: Inapproximability results for SAT and other problems
Z3: An Efficient SMT Solver → supportsFeature → Max-SAT ⓘ
subject surface form: Z3
this entity surface form: MaxSMT