I have the two following questions:
I know SAT -> MAX-SAT but how can I show that if MAX-SAT is solved in polynomial time then SAT is solved in polynomial time as well?(I guess using approximation algorithms)
I have this simple randomized algorithm for approximating the MAX-SAT problem:
The algorithm sets each variable to be True independently with probability 1/2 and False with probability 1/2. It then outputs the resulting assignment.
for(i=1,2,...,n){
set xi = 0 or xi = 1 with probability 1/2 for each case
}
So everywhere I have looked I found people presenting this as an 1/2 approximation algorithm but I'm supposed to prove that this is a 2 approximation algorithm. Can anyone help clarify this?