In the MAX SAT problem, we are given a set of clauses. $$\sum_{j=1}^m 1-(\tfrac12)^{k_j} \; \ge m/2
MAX SAT prob- polynomial time
1
$\begingroup$
algorithms
-
0What are your thoughts? For example if you do "the stupidest thing you can think of that doesn't _obviously_ lead nowhere" in (a), where do you get stuck? – 2012-12-02
-
0b is more of a question to me than a – 2012-12-02
-
0And what are your thoughts on that, then? – 2012-12-02