4
$\begingroup$

Is there a proof that linear programming is in $coNP$ without showing it is in $P$?

If so what is the strategy?

$\endgroup$
3
  • 4
    $\begingroup$ Farkas' lemma guarantees the existence of a rather succinct certificate of infeasibility, namely that there is a linear combination of the inequalities that derives $0 \geq 1$. $\endgroup$ – Yonatan N Sep 22 '20 at 5:47
  • $\begingroup$ @YonatanN Could you post a full answer? $\endgroup$ – 1.. Sep 22 '20 at 8:33
  • 3
    $\begingroup$ This is a standard question that is easily found in books and lecture notes. $\endgroup$ – Chandra Chekuri Sep 22 '20 at 14:26
9
$\begingroup$

Note: all vector inequalities in this reply are to be interpreted pointwise.

Given a linear feasibility problem, you can always rewrite it in the following canonical form: given a matrix $A \in \mathbb{R}^{m \times n}$ and vector $b \in \mathbb{R}^m$, does there exist an $x \geq \vec{0}$ such that $Ax \leq b$?

Farkas' lemma states that when a system of inequalities such as the above has no solution, then there exists a "witness" vector $y \in \mathbb{R}^{m}$ such that

  1. $y \geq \vec{0}$,
  2. $A^{\intercal}y \geq \vec{0}$, and
  3. $b^{\intercal}y < 0$.

Effectively, $b$ gives you a nonnegative scaling factor for each constraint, such that when you add up all of the scaled constraints, the left-hand side ends up with a sum of a bunch of nonnegative terms, and the right-hand side ends up with a strictly negative value. That is, $y$ provides a direct way to prove that the inequalities are inherently contradictory.

Therefore, the existence of such a $y$ is both a necessary and sufficient condition for any given problem instance to be infeasible, meaning that it can be used as a polynomial-time checkable certificate of infeasibilty. So linear feasibility checking is in co-NP.

$\endgroup$
4
  • 1
    $\begingroup$ Why is the number of bits polynomial? $\endgroup$ – 1.. Sep 23 '20 at 23:18
  • $\begingroup$ Farkas' lemma is essentially a statement about the dual of the given linear feasibility problem subject to a zero-objective function: it tells you that the dual has a feasible solution, with an unbounded negative objective value. So one way (hypothetically) to find a satisfying $y$ is by solving a linear program of the same size as the original input, meaning that we can borrow known results on the bit complexity of solutions to LPs (e.g. from page 1 here), even as as we avoid the actual poly-time algorithm itself . $\endgroup$ – Yonatan N Sep 24 '20 at 3:25
  • $\begingroup$ I do not see why $y$ has to be polynomial in total bit length. $\endgroup$ – 1.. Sep 25 '20 at 3:23
  • $\begingroup$ As mentioned in the previous comment, one choice of $y$ is given by a solution to a (feasible) linear program. For example, minimize $b^Ty$ subject to $A^Ty\geq \vec{0}$, $y \geq \vec{0}$, $|y|_1 \leq 1$ (the last inequality is not strictly necessary, it's just there to make the program bounded, and any other solution can be rescaled to this by dividing by $|y|_1$ so we have not changed the feasibility of the LP). Basic feasible solutions to bounded linear programs have polynomial total bit length when expressed as fractions (see link in previous comment), so this choice of $y$ does as well. $\endgroup$ – Yonatan N Sep 25 '20 at 7:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.