P,NP

these are classes of language/decision problems.

decision problems.(결정 문제)

문제의 답을 예 혹은 아니오로 답할 수 있는 문제. 
*따라서 흔히 말하는  최적화문제는 결정 문제가 아니다. 최적화문제는 P나 NP에 속한다고 말하는 것이 아니다. 다만,
최적화 문제를 그에 상응하는 결정문제로 바꾸거나 역으로 만들 수 있다. 

어떤 문제를 푸는 알고리즘의 time complexity 가 polynomial time 일 때 (그런 알고리즘이 존재할 때) 그 문제는  P에 속한다고 말한다.

time complexity

: 주어진 입력크기 n에 대해 걸리는 시간들중 최대 값으로 대응시키는 함수로 표현한다. 이 함수를 f 라고 하면,
time complexity 가 polynomial time 이라는 것은 n에 관한 적당한 다항식 p(n)이 존재해서 f(n) < = p(n)  임을 의미한다.

어떤 문제를 푸는 nondeterministic 알고리즘이 polynomial time 으로 동작하면 (그런 알고리즘이 존재할 때) 그 문제가 NP 에 속한다고 말한다.


nondeterministic 알고리즘은 주어진 입력에 대해 (1) 답을 추측하는 단계 와 (2) 답이 맞는 지 확인하는 단계 로 나뉘어 진다.
이 때, 추측과정에서 생성한 답을 정확하게 검증한다면, 그 문제를 푼다고 얘기 한다.

nondeterministic 알고리즘이 polynomial time 으로 동작한다는 것은 여기서  단계 (2) 에 걸리는 시간이 polynomial time 이라는 것이다.