I am referring to the natural decision version of the Linear Programming problem: given $A \in \mathbb{Q}^{m \times n}, \ b \in \mathbb{Q}^m, \ c \in \mathbb{Q}^n, \ \alpha \in \mathbb{Q}$, does there exist $x \in \mathbb{Q}^n$, s.t. $Ax=b, \ x \geq 0, \ c^T x \geq \alpha \ ?$
Most ressources I know justify that $LP$ is in $coNP$ by referring to the dual problem: a certificate that such an $x$ does not exist consists of an optimal basis for the dual problem. A verifier can then check in polynomial time that the associated dual solution fulfills all dual constraints and that it has cost $<\alpha$.
However, I'm wondering: why couldn't we certify that such an $x$ does not exist by providing an optimal basis $B$ for the primal problem? It is well known from the revised simplex algorithm (see e.g. here for explanation of notations) that $x$ is optimal for the primal iff $(c_N - N^T (B^{-1})^T c_B) \leq 0$, and this can be verified in polynomial time. Therefore, we just need to check this condition and also that $c^T x < \alpha$. This gives an argument for $LP \in coNP$ that does not require knowing duality theory.
I am aware that if $x$ is optimal for the primal, then the vector $(c_N - N^T (B^{-1})^T c_B)$ is actually a solution of the dual, which makes my argument in essence equivalent to the classical argument that explicitly uses duality theory. Still, I'm wondering 1. whether what I've written here is correct and 2. why no one mentions this simple way to show $LP \in coNP$ in the literature.
