NonDeterministicPolynomial time soluble.

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

두가지가 있다.

• NP-complete : TSP -> decision problem

• NP-hard : optimazation problem

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

• GeneticAlgorithm

• NeuralNetwork

SeeAlso P=NP?