« To prove NP completeness: (1) Ask if the problem can be discretized, e.g. ability to break analog audio into discreet samples. If no, may be NP complete. (2) Is there a finite way to solve this (even if looping/recursion involved)? Can the problem always be solved this way? E.g. using recursive calls to find Fibonacci numbers at nth place. If no, NP complete (though further analysis may make this into sub-function of larger algorithm). (3) Is the solution always the same no matter what tweaks are made? If no, the problem has many routes to solve it. E.g. FFT analysis since FFTs can vary in accuracy of frequency analysis, allowing some speed. » ~ From an undergraduate midterm exam.
Proving NP-CompletenessNovember 20, 2010