Proof of $LP$ is in $coNP$ without showing it is in $P$? Is there a proof that linear programming is in $coNP$ without showing it is in $P$?
If so what is the strategy?
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 &quot;witness&quot; vector $y \in \mathbb{R}^{m}$ such that

$y \geq \vec{0}$,
$A^{\intercal}y \geq \vec{0}$, and
$b^{\intercal}y &lt; 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.