NonDeterministicPolynomial time soluble.

ComputationalComplexity가 높은 문제. 현재의 컴퓨터인 TuringMachine은 이 문제를 푸는데 오래걸린다.

두가지가 있다.
 * [[NP]]-complete : [[TSP]] -> decision problem
 * [[NP]]-hard : optimazation problem

따라서, HeuristicAlgorithm 같은 다른 방법들이 도입된다. 
 * GeneticAlgorithm
 * NeuralNetwork

SeeAlso [[http://www.math.snu.ac.kr/~hongjong/%C0%E2%C7%CA/PversusNP/PversusNP.html|P=NP?]]