P: The problems that can be solved in polynomial time.
NP: The problems whose solutions can be verified in polynomial time.
NP-complete: The problems in the set of NP problems and also in the set of NP-hard problems.Although any given solution to such a problem can be verified quickly, there is no known efficient way to locate a solution in the first place; indeed, the most notable characteristic of NP-complete problems is that no fast solution to them is known. What makes NP-complete problems important is that if a deterministic polynomial time algorithm can be found to solve one of them, every NP problem is solvable in polynomial time (one problem to rule them all).--Cook's theorem.
NP-hard: The problems that are at least as hard as NP-complete problems. NP-hard problems do not have to be in NP.
Usually there are three kinds of algorithms to solve NP-complete and NP-hard problems: 1. Backtracking algorithms with good prunning techniques.2. Heuristic algorithms.3. Approximation algorithms.
Differences between heuristic algorithms and approximation algorithms areapproximation algorithms are like putting money in the banks -- you alwaysget 3% benefit a year (approximation algorithms always return solutions with a guarantee attached, you can never go too far wrong when using them)Heuristic algorithms are like putting your money into the stock market, you may do much better than approximation algorithms or even get the optimal solution, but they are without guarranty.
转载于:https://www.cnblogs.com/tanghulu321/archive/2013/05/20/3088060.html
