Re: proof regarding 3-SAT


Tom wrote:
I've been told that for any instance of 3-SAT there is an
interpretation that satisfies at least 7/8 of the clauses. So if there
are m clauses then 7m/8 can be satisfied.
I am trying to prove this and need some help getting started. Any help
or hints would be appreciated.

Flip a coin for each variable.

--- Christopher Heckman

P.S. It has been proven that if 7/8 can be improved, then P = NP.

.