Lecture 20
Tuesday, July 25, 2017
10:46 PM
Remarks:
The classification of algorithms into Greedy, DP, etc. is just for convenience. It's OK to create hybrid algorithms.
 NP-complete problems provide a source of many natural problems we don't know how to solve with efficient algorithms. A common belief is that no such algorithms exist (i.e., that P is not equal to NP), but we don't really know!
 Randomized (and quantum) polytime algorithms extend our notion of efficient algorithms (from the usual deterministic polytime algorithms).
 Our ideal algorithm for a given problem is 
fast (polytime), and
correct on all inputs of that problem.