## Homework #2

Homework #2 (and exercises) now on the webpage.  It’s due in a week, i.e., next Thursday (9/29). And again, ask questions and make comments on the homework in the comments below.

Clarification: for problem #3, feel free to use the result of Hwk2(#1) that we can reduce the search version of feasibility to the decision version.

### 3 Comments to “Homework #2”

1. I think the first part of problem 5 seems to leave open using an LP formulation for which I don’t see a better value than OPT. IE, rather than letting the clause’s value be bounded by some sum of variables, what if they’re bounded by a max of sum variables? Then I’m thinking that I don’t have the right LP for what you want… there are obviously several LP formulations of MAX-SAT with 1 variable/clause and 1 variable/ variable.

I figured out the one you want, but I think it might be wise to be slightly more specific. In the case that your clause variables are equal to a max of things, you won’t have the problem that you’ll ever have a setting of variables which set your clause value to 1 unless a variable is set to 1.

2. Hi Jamie. If you think you have an LP formulation of the Max-Sat problem with the property that LPOpt = Opt, then I guess you probably don’t… Max-Sat is NP-hard so this would show NP = P. Maybe you should double-check that the formulation you have can really be expressed an LP: optimizing a linear function subject to linear inequalities…

3. My LP formulation didn’t have LPOPT = OPT, it did have the property that you couldn’t (with 4 clauses) get a full integer larger value for LPOPT, since each clause variable was taking on a max of things in [0,1] rather than a sum of variables in [0,1] (thus, any clause variable would be 1 iff one of the variables were set to 1).