# Car Production

(otherwise known as 15-451 Extra Credit)

1. Binary LPs. Binary Linear Programming is like linear programming, with the additional constraint that all variables must take on values either 0 or 1. The decision version of binary linear programming asks whether or not there exists a point satisfying all the constraints.

Show that BinLP is NP-complete.

• Roses are red, carnations are another
• We’ll first reduce from vertex cover

• Let the problem be $k, (V, E)$
• Then make $y_v$ for $v$ in $V$

• Now consider the constraints below
• That gives us one more thing to show:
\begin{aligned} \sum_{v \in V} y_v &\le k & \\ y_v + y_u &\ge 1 & (u,v) \in E \end{aligned}
• An edge $(u,v)$ sum’s satisfied, when
• $y_v = 1$ or $y_u = 1$, then

• These correspond to $v$ or $u$
• Being chosen, or maybe both, too

• So once we’ve solved this problem we’re done
• $v$’s in the cover when $y_v$’s 1

• The first constraint now saves the day
• It bounds the cover by at most $k$

• Next’s to prove we’re in NP
• But that part’s pretty clear to me

• Just take the given solution set,
• Add’em up, they’ll work, I bet

• So BinLP’s both hard and in NP
• Therefore, QED