In the paper "Some NP-complete problems in linear programming" (https://doi.org/10.1016/0167-6377(82)90006-2), there are several proofs given to show that testing for degeneracy in LPs is NP-complete. I don't understand the proof in section 4. Are they saying that their reduction only produces binary y values? Or are they introducing a binary variable (and thus invalidating their proof)? The statement of "the standard trick..." -- what is this trick? Does it have a name? Is someone able to write out this "combined system (5)" for me? What does it look like?

enter image description here



Your Answer

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