Maximum Satisfiability Problem
Jump to navigation
Jump to search
See: Boolean Satisfiability Problem, MAX-SAT, MaxSAT, MAX-2SAT, MAX-3SAT.
References
2011
- http://en.wikipedia.org/wiki/Maximum_satisfiability_problem
- In computational complexity theory, the Maximum Satisfiability problem, or MAX-SAT, is the problem of determining the maximum number of clauses, of a given Boolean formula, that can be satisfied by some assignment. The MAX-SAT problem is NP-hard, since its solution easily leads to the solution of the boolean satisfiability problem, which is NP-complete. In particular [math]\displaystyle{ O(NP^{log}) }[/math] for unweighted, and [math]\displaystyle{ O(NP^{NP}) }[/math] for weighted. From another point of view, it is also APX-complete, and thus does not admit a PTAS unless P = NP. MAX-SAT is one of the optimization extensions of the boolean satisfiability problem, which is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE. If the clauses are restricted to have at most 2 literals, as in 2-satisfiability, we get the MAX-2SAT problem. If they are restricted to at most 3 literals per clause, as in 3-satisfiability, we get the MAX-3SAT problem.
- http://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Extensions_of_SAT
- … The maximum satisfiability problem, an FNP generalization of SAT, asks for the maximum number of clauses which can be satisfied by any assignment. It has efficient approximation algorithms, but is NP-hard to solve exactly. Worse still, it is APX-complete, meaning there is no polynomial-time approximation scheme (PTAS) for this problem unless P=NP.
2004
- Cohen, Cooper, Jeavons. A complete characterization of complexity for boolean constraint optimization problems. CP 2004.
1994
- Christos Papadimitriou. Computational Complexity. Addison-Wesley, 1994
1986
- Mark Krentel. The Complexity of Optimization Problems. 1986. ACM.
1973
- D. S. Johnson. (1973). “Approximation algorithms for combinatorial problems.” In: Proceedings of the fifth annual ACM symposium on Theory of computing.