NonDeterministicPolynomial time soluble.

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

두가지가 있다.

  • NP-complete : TSP -> decision problem

  • NP-hard : optimazation problem

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

SeeAlso P=NP?

web biohackers.net