Related Problems
MAX-3SAT(B) is the restricted special case of MAX-3SAT where every variable occurs in at most B clauses. Before the PCP theorem was proven, Papadimitriou and Yannakakis showed that for some fixed constant B, this problem is MAX SNP-hard. Consequently with the PCP theorem, it is also APX-hard. This is useful because MAX-3SAT(B) can often be used to obtain a PTAS-preserving reduction in a way that MAX-3SAT cannot. Proofs for explicit values of B include: all B ≥ 13, and all B ≥ 3 (which is best possible).
Moreover, although the decision problem 2SAT is solvable in polynomial time, MAX-2SAT(3) is also APX-hard.
The best possible approximation ratio for MAX-3SAT(B), as a function of B, is at least and at most, unless NP=RP. Some explicit bounds on the approximability constants for certain values of B are known.
MAX-EkSAT is a paramaterized version of MAX-3SAT where every clause has exactly literals, for k ≥ 3. It can be efficiently approximated with approximation ratio using ideas from coding theory.
Read more about this topic: MAX-3SAT
Famous quotes containing the words related and/or problems:
“In the middle years of childhood, it is more important to keep alive and glowing the interest in finding out and to support this interest with skills and techniques related to the process of finding out than to specify any particular piece of subject matter as inviolate.”
—Dorothy H. Cohen (20th century)
“I conceive that the leading characteristic of the nineteenth century has been the rapid growth of the scientific spirit, the consequent application of scientific methods of investigation to all the problems with which the human mind is occupied, and the correlative rejection of traditional beliefs which have proved their incompetence to bear such investigation.”
—Thomas Henry Huxley (1825–95)