HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Hardness of Approximation of MAX-3SAT

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
3satmaxapproximationhardness

Problem

This is probably a duplicate of this question, but I need a somewhat blunter answer. Let's say I have a polynomial time algorithm that finds an assignment that satisfies more than $\frac{7}{8}$ of the clauses of a satisfiable 3SAT instance. Do I collect my million dollars from the Clay Institute for proving $P=NP$?

Solution

I believe that Håstad gave such an algorithm in 2000, see On bounded occurrence constraint satisfaction. His algorithm is stated for instances where each variable occurs at most $B$ times, and the advantage over 7/8 depends on $B$. The running time, however, seems not to depend on $B$.

In order to prove that P=NP, you need to find an algorithm which, given a satisfiable instance, satisfies at least $7/8+\epsilon$ clauses, for some constant $\epsilon>0$. This will enable you to distinguish between satisfiable instances and instances which are at most $7/8+\epsilon/2$ satisfiable, which is NP-hard as my answer to the question you mention shows.

Context

StackExchange Computer Science Q#71040, answer score: 3

Revisions (0)

No revisions yet.