This is a hard reduction that I’m not sure I understand. I’m sure if I was better at vector operations, I’d be more able to figure it out.

**The problem: **Cost-Parametric Linear Programming. This is problem MP3 in the appendix.

**The description: **Given a set of integer constraints (,b) as in Integer Programming, (except that the inequalities are instead of for some reason, but we can always multiply by -1 to flip the constraints) and a set J that is a subset of indices of the variables in . Can we find an m-tuple with rational values such that q and for all feasible non-negative m-tuples that satisfy the constraints, the minimum of >

**Example: **Ok, here’s a pretty simple situation. Suppose we have 3 variables, with constraints:

(Or, technically, )

Now, suppose we choose a of (1,1,0} and a J of {1,2}. So in this case, the minimum of would be .3 + .4 = .7. That needs to be more than This comes out to .5 + 0, so it works. So, with this , we need q , so a q > makes this solution correct. There may be different values for that will also work on smaller q’s.

**Reduction: **G&J say that the reduction is from 3SAT, but I think the paper by Jersolow uses DNF Non-Tautology. Given a logical formula in DNF form, he builds a linear inequality system. All variables in formula become variables in the linear program. For each clause, every variable has a constraint that it’s 1. (and, I think implicitly, 0). If the variable shows up in a literal positively, we add the constraint that it is 1. If it shows up negatively, we have a constraint that it’s 0. This means that we have a solution to the constraints if and only if we set the variables to the truth values that make the clause true. (Remember, we have a DNF formula, so each clause is a conjunction- we need to make each variable true).

He then shows that the minimum way to solve the constraints (since it’s in DNF, that means making one clause true) is is true for all if and only if A is a tautology. From there he goes on to show that our problem instance holds.

I’m pretty confused by the logic- especially seems it looks like he’s saying that his problem is true if and only if the original problem *is* a tautology, when *non-*tautology is what we’re supposed to be reducing from.

**Difficulty **9. This is a hard problem to understand, and the reduction is hard to follow as well. It’s very possible I’m not understanding something in the paper.