Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
MAX-3SAT
open-in-new
<p>MAX-3SAT is a problem in the <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity</a> subfield of <a href="/facts/Computer_science/lN3pEyPz">computer science</a>. It generalises the <a href="/facts/Boolean_satisfiability_problem/wBVRjWoy">Boolean satisfiability problem</a> (SAT) which is a <a href="/facts/Decision_problem/cQNWjbdE">decision problem</a> considered in <a href="/facts/Computational_complexity_theory/etHuVF3U">complexity theory</a>. It is defined as: </p><p><i>Given a <a href="/facts/3-CNF/B3sY1lTW">3-CNF</a> formula Φ (i.e. with at most 3 variables per clause), find an assignment that satisfies the largest number of clauses.</i> </p><p>MAX-3SAT is a canonical <a href="/facts/Complete_(complexity)/Ine1b8Qy">complete</a> problem for the complexity class <a href="/facts/MAXSNP/nKmjs3qz">MAXSNP</a> (shown complete in Papadimitriou pg. 314). </p>