Complexity Explorer Santa Fe Institute

1) Divide-and-conquer can't be used to eciently solve all problems.

True - Some problems, in particular NP-complete problems, seem to be not amenable to divide-and-conquer. And of course, divide-and-conquer doesn't help us solve uncomputable problems like the halting problem.

 

2) Greedy algorithms always succeed because they make the best choice

at each step.

False - There are problems that are not amenable to greedy algorithms. Most notably, NP-complete problems seem to have this property. In particular, the "best'' choice at one step may force you down a path where, although the algorithm made the best choice at each step, the resulting solution is not optimal.

 

3) For max-flow, by allowing moves which "push flow backwards''---while respecting the constraint that no edge ever has negative flow---you can always reach the global optimum by the greedy algorithm.

True - True (for an explanation see the lecture video)

 

4) For any optimization problem, you can add allowable moves such that the resulting greedy algorithm always finds the global optimum. 

False - As with the preceding questions, consider NP-complete problems, or even uncomputable optimization problems.