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.

  • 2
    $\begingroup$ Your idea for a certifying optimality seems correct. I haven't seen it presented this way. I also agree that the fact that local optimality implies global optimality seems more accessible than duality. On the other hand, to understand the concept of a basis, and what local optimality looks like in terms of a basis, is perhaps not more accessible (for those not yet familiar with either) than duality. $\endgroup$
    – Neal Young
    Commented May 19, 2021 at 18:15


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.