My professor has asked me to prove the following:

Prove that we can use an algorithm for linear programming to solve linear inequality feasibility problems. The number of variables and constraints used in the linear programming problem must be polynomial in n and m

I supplied him with an intuitive proof but he has asked me to rewrite it into a formal proof. My question is: How does one turn an intuitive proof into a formal proof?

Here is my proof:

To prove that a linear programming algorithm can solve the linear inequality feasibility problem, let us consider what one would need to solve the linear inequality feasibility problem. We need a value that will satisfy every inequality. To find that, one could theoretically find every value that satisfies every individual inequality and then find the intersection. Because this is generally unfeasible in polynomial time, we can use a cartesian plane to greatly reduce the computation time and still represent all the values we computed using the first method. To do this all we would need to do is to is plot the inequalities and then shade the part of the inequality that contains the feasible values. Repeat this process until all the inequalities have been plotted. If there is a value or values, it will be in the region that has been shaded by all the inequalities. The process we have just described is a linear programming algorithm, therefore the linear inequality feasibility problem can be solved by a linear programming algorithm.

NOTE: In my proof, I talk about using a Cartesian plane. I know that that is incorrect for an inequality of more than 3 variables and that I should say instead that we should be using $\mathbb{R}^n$ where n is equal to the number of variables but I didn't know how to word that into my proof.

Thanks a mil.

  • $\begingroup$ What you describe is a "non-black-box reduction": you are showing how a particular algorithm for linear programming can be modified to solve the feasibility problem. However, the question asks you for a "black-box reduction", in which you use a "black-box" that can solve linear programming in order to solve your problem. $\endgroup$ Mar 5, 2017 at 16:17
  • $\begingroup$ What does "linear programming" mean for you? Usually the input is a linear program, and the output is either the value of the program, or "unfeasible", or "unbounded". Sometimes we also want an optimal solution, or a certificate for unfeasibility or unboundedness. Given such an algorithm, it is trivial to solve linear inequality feasibility (by adding a dummy objective). Perhaps you have a different formalism in mind? $\endgroup$ Mar 5, 2017 at 16:18
  • $\begingroup$ Finally, note that you argument is (1) not a proof in any way, (2) doesn't seem to give an efficient algorithm, though it's hard to know since the description is rather vague. $\endgroup$ Mar 5, 2017 at 16:19
  • $\begingroup$ @YuvalFilmus Thank you for given me all of this to think about. I'd like clarification on a couple of things. (1) So are you saying that if I can modify the input of this problem to conform to what a general linear programming input looks like, it would imply that the problem could be solvable with a linear programming algorithm? (2) What am I missing from my argument to make it a complete proof? $\endgroup$
    – Gab
    Mar 5, 2017 at 17:26
  • 1
    $\begingroup$ @GabrieleB-David To provide guidance, instead of critique. A key aspect of proving things is that proofs proceed from definitions. You should be giving definitions and your proof should connect to those definitions. In this case, you want to show from the definition of "linear programming" you can construct an algorithm that meets the definition of "solving linear inequality feasibility". Step 1 will be defining those two terms. Step 2 will be making the construction. Step 3 will be showing that your construction meets the definition of "solving linear inequality feasibility". $\endgroup$ Mar 5, 2017 at 23:45


Your Answer

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

Browse other questions tagged or ask your own question.