On the Computational Complexities of Finding Selected Refutations of Linear Programs

In this paper, we establish the computational complexities of selected forms of refutations of linear programs. Linear programming is in the complexity class P and hence, it must have short affirmative and disqualifying certificates. One of the more celebrated lemmata in linear programming is Farkas’ lemma, which establishes that both “yes" and “no" certificates can be thought of as solutions to complementary linear programs. Since then, it has been established that if a linear program is feasible, then it must have a solution which is bounded by a polynomial function of the input size. The latter observation, coupled with Farkas’ lemma, immediately establishes that linear programming is in NP \(\cap \) coNP. Our goal is to study the computational complexities of determining various constrained refutations for a given linear programming problem. This paper focuses on three distinct refutation forms, viz., read-once, tree-like and dag-like. We establish that checking if a linear program has a read-once refutation is NP-complete, even when it is defined by Binary Two Variable Per Inequality (BTVPI) constraints. Furthermore, the problems of finding the shortest tree-like and dag-like refutations are NPO-complete and NPO PB-complete respectively.