"This is Hard"
Nancy Dujmovic 2005
Abstract
One of the great topics in theoretical computer science is the subject of NP complete problems. The class NP is the set of problems that are solvable with a nondeterministic polynomial algorithm. In other words, the algorithm can run in polynomial time, but there are many possibilities that the algorithm could take at a given step. To contrast, the class P is the set of problems that can be solved with a polynomial deterministic algorithm.
An NP-hard problem is a problem that, if solved in polynomial time, can be reduced to solve any problem in the class NP. In other words, if there is an NP-hard problem in the class P, then NP=P. A problem is NP-complete if it is in the class NP and is NP-hard. Examples of NP-complete problems include the Traveling Salesman Problem (TSP for short), the Boolean Satisfiability problem (SAT for short), and the Vector Coloring and Minimum Vector Cover problems.
This paper explains the history of NP-complete problems and the research that has been done to find approximation algorithms, analyze the current runtimes of algorithms that solve NP-complete problems, and finally analyze approximation algorithms that find a “good” answer in polynomial time.