Complexity Explorer Santa Fe Institute

Your progress is not being saved! Enroll now or log in to track your progress or submit homework.

Introduction to Computation Theory

Lead instructor:


7.2 Heuristics 2 » Quiz Explanation

1) The simplex algorithm shows that linear programming is in $\mathsf{P}$.

False - There are instances on which the simplex algorithm takes exponential time. In fact, it has been proved to be what is called "-mighty''. However, the smoothed analysis of Spielman and Teng shows that, on any input, we can modify the input by an arbitrarily small amount to find an instance on which the simplex algorithm runs in polynomial time.

 

2) The fact that linear programming is in P (which it is) does not show P = NP.

True - integer linear programming is NP-complete, but linear programming is not. A polynomial-time algorithm for integer linear programming would indeed show P=NP.

 

3) Approximation algorithms nd solutions that, while not optimal, look like the optimal solution.

Approximation algorithms only guarantee that the value being optimized will be within some factor of the optimum value. They do not guarantee that the solution they find looks anything like the optimal solution.