P, NP, NP-hard, NP-complete

P (deterministic polynomial time)는 다항시간 내에 답을 구할 수 있는 문제들의 집합.

NP 는 다항 시간 내에 답을 구할 수 있는 비결정적(Nondeterministric) 알고리즘이 존재하는 decision problem의 집합. (NP : Nondeterministric Polynomially bounded)

NP-hard 는 모든 NP의 문제들이 polynomial time 내에 문제 H로 환산될 수 있는 문제 H들의 집합.( reducible )

NP-complete 는 NP에 속하면서, 모든 NP에 대해 polynomial-time내에 reducible 한 문제들의 집합. NP-complete에 해당하는 문제는 그들 중 단 한 문제에 대한 효율적인 알고리즘이 존재한다는 것이 증명되면 다른 모든 문제에 대한 효율적 알고리즘도 존재하게 된다. 어떤 문제가 NP-complete임을 아는 것은 상당히 중요한게, 어떤 문제가 NP-complete임을 모르고 그 문제에 대한 최적해를 구하려고 하면 별 성과가 없을 것이기 때문. 반면 어떤 문제가 NP-complete임을 보일 수 있으면 어느 정도 좋은 성능을 보여주는 쓸만한 알고리즘을 개발하는 데 시간을 투자할 수 있기 때문이다. 유명한 NP-complete 문제로는 “순회 판매원 문제”가 있다.

* NP-hard는 적어도 NP만큼은 어렵다. * 환산(reduction) : 보통 “A->B로 환산 가능하면 B는 적어도 A만큼 어렵다”를 보이는데 사용된다.

NP-hard이면서 NP가 아닌 예 :정지문제

프로그램을 설명한 것과 처음 입력값이 주어졌을 때, 이 프로그램에 입력값을 넣고 실행한다면 이 프로그램이 계산을 끝내고 멈출지 아니면 영원히 계속 계산할지를 판정하는 일반적인 알고리즘이 존재하는가?
“~을 판정하라”이지만 판정이 불가능하다.