Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Maximum satisfiability problem
open-in-new
<p>In <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, the maximum satisfiability problem (MAX-SAT) is the problem of determining the maximum number of clauses, of a given <a href="/facts/Propositional_formula/eEV8YrAI">Boolean</a> formula in <a href="/facts/Conjunctive_normal_form/B3sY1lTW">conjunctive normal form</a>, that can be made true by an assignment of truth values to the variables of the formula. It is a generalization of the <a href="/facts/Boolean_satisfiability_problem/wBVRjWoy">Boolean satisfiability problem</a>, which asks whether there exists a truth assignment that makes all clauses true. </p>