|
MAX-3SAT is a problem in the computational complexity subfield of computer science. It generalises the Boolean satisfiability problem (SAT) which is a decision problem considered in complexity theory. It is defined as: ''Given a 3-CNF formula Φ (i.e. with at most 3 variables per clause), find an assignment that satisfies the largest number of clauses.'' MAX-3SAT is a canonical complete problem for the complexity class MAXSNP (shown complete in Papadimitriou pg. 314). == Approximability == The decision version of MAX-3SAT is NP-complete. Therefore, a polynomial-time solution can only be achieved if P = NP. An approximation within a factor of 2 can be achieved with this simple algorithm, however: * Output the solution in which most clauses are satisfied, when either all variables = TRUE or all variables = FALSE. * Every clause is satisfied by one of the two solutions, therefore one solution satisfies at least half of the clauses. The Karloff-Zwick algorithm runs in polynomial-time and satisfies ≥ 7/8 of the clauses. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「MAX-3SAT」の詳細全文を読む スポンサード リンク
|