<p>Note: all vector inequalities in this reply are to be interpreted pointwise.</p>
<p>Given a linear feasibility problem, you can always rewrite it in the following canonical form: given a matrix <span class="math-container">$A \in \mathbb{R}^{m \times n}$</span> and vector <span class="math-container">$b \in \mathbb{R}^m$</span>, does there exist an <span class="math-container">$x \geq \vec{0}$</span> such that <span class="math-container">$Ax \leq b$</span>?</p>
<p>Farkas' lemma states that when a system of inequalities such as the above has no solution, then there exists a &quot;witness&quot; vector <span class="math-container">$y \in \mathbb{R}^{m}$</span> such that</p>
<ol>
<li><span class="math-container">$y \geq \vec{0}$</span>,</li>
<li><span class="math-container">$A^{\intercal}y \geq \vec{0}$</span>, and</li>
<li><span class="math-container">$b^{\intercal}y &lt; 0$</span>.</li>
</ol>
<p>Effectively, <span class="math-container">$b$</span> 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, <span class="math-container">$y$</span> provides a direct way to prove that the inequalities are inherently contradictory.</p>
<p>Therefore, the existence of such a <span class="math-container">$y$</span> 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.</p>

CC BY-SA 4.0
2020-09-23T23:18:09.007Z
Why is the number of bits polynomial?
Turbo
CC BY-SA 4.0
2020-09-24T03:25:07.467Z
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](https://people.orie.cornell.edu/dpw/orie6300/fall2008/Lectures/lec19.pdf)), even as as we avoid the actual poly-time algorithm itself .
Yonatan N
CC BY-SA 4.0
2020-09-25T03:23:19.760Z
I do not see why $y$ has to be polynomial in total bit length.
Turbo
CC BY-SA 4.0
2020-09-25T07:26:38.667Z
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.
Yonatan N
CC BY-SA 4.0
2020-09-22T09:42:11.530Z
2020-09-23T05:51:11.510Z
2020-09-23T05:51:11.510Z
Yonatan N
<p>Is there a proof that linear programming is in <span class="math-container">$coNP$</span> without showing it is in <span class="math-container">$P$</span>?</p>
<p>If so what is the strategy?</p>

CC BY-SA 4.0
2020-09-22T05:47:52.927Z
[Farkas' lemma](https://en.wikipedia.org/wiki/Farkas%27_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$.
Yonatan N
CC BY-SA 4.0
2020-09-22T08:33:37.023Z
@YonatanN Could you post a full answer?
Turbo
CC BY-SA 4.0
2020-09-22T14:26:03.367Z
This is a standard question that is easily found in books and lecture notes.
Chandra Chekuri
<cc.complexity-theory><linear-programming>
Proof of $LP$ is in $coNP$ without showing it is in $P$?
Turbo
# Proof of $LP$ is in $coNP$ without showing it is in $P$?

(Asked by: username_0 on 2020-09-22)

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

If so what is the strategy?

**Tags:** cc.complexity-theory, linear-programming
> **Comments:**
> **username_1**: [Farkas' lemma](https://en.wikipedia.org/wiki/Farkas%27_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$.  
> **username_0**: @YonatanN Could you post a full answer?  
> **username_2**: This is a standard question that is easily found in books and lecture notes.  

---

## 1 answers

### Answer by username_1 on 2020-09-22. Score: 9

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.

> **Comments:**
> **username_0**: Why is the number of bits polynomial?  
> **username_1**: 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](https://people.orie.cornell.edu/dpw/orie6300/fall2008/Lectures/lec19.pdf)), even as as we avoid the actual poly-time algorithm itself .  
> **username_0**: I do not see why $y$ has to be polynomial in total bit length.  
> **username_1**: 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.  

---

