Maximum 2-satisfiability
= Maximum 2-satisfiability
= MAX-2SAT
{c}
{synonym}
Maximum 2-satisfiability asks for an assignment satisfying as many <clause> occurrences as possible when every nonempty <clause> has at most two <literals>. Occurrences are counted even when a <clause> is repeated. Its decision problem is <NP-complete> by the <seven-clause gadget for MAX-2SAT>, while the <method of conditional probabilities> gives a polynomial-time half approximation.