P: Polynomial time 이내에 해결 가능한 알고리즘을 말한다. 즉, 알고리즘의 복잡도가 O(n$^x$)로 표현되는 모든 문제들을 말한다.

→ 즉 (일반적인 컴퓨터와 같은) 튜링 머신이 다항 시간내에 풀어낼 수 있는, 쉬운 문제를 의미한다. ex) 정렬 문제(sort)

NP: Non-deterministic Polynomial의 약자로, Polynominal time에 답의 존재유무를 확인할 수 있는 문제를 말한다.

→ 결정론적 튜링머신으로 다항 시간에 풀어낼 수 있는 문제들을 NP 문제라고 한다.

• Polynominal time(다항시간): 다항시간 내에 풀 수 있다는 의미는, 시간 복잡도가 O(n^2), O(n^3)같이 O(n^k)로 표현될 수 있다 는 의미이다.
• Decision problem(보고결정 문제): Yes or No로 답하는 문제

→ 이 결정 문제를 다항식 시간에 풀 수 있는 문제들의 집합을 P라고 한다. (P는 Yes나 No라는 답을 다항식 시간에 낼 수 있는 문제군이다.)

→ 이때 NP는 문제의 답이 Yes라는 근거가 주어지면 그것이 옳다는 것을 다항식 시간에 증명해줄 수 있는 문제이다.

⇒ P는 NP의 부분집합이 된다.

→ 만약 어떤 P 문제가 주어졌고, 그 문제의 답이 YES라면, 우리는 그 문제의 답에 관한 힌트가 주어지면 곧바로 그 문제의 답이 YES라는 것을 쉽게 확인할 수 있을 것이므로, 모든 P 문제는 저절로 NP 문제도 된다. 즉, P⊂NP임을 알 수 있다.

→ 그 역방향인 NP⊂P에 대해서는 참인지 거짓인지 아직 알려져 있지 않다. 만약 모든 NP 문제가 P 문제인 경우, 즉 모든 NP 문제가 다항 시간에 풀 수 있는 알고리즘이 존재함을 증명할 경우 P=NP라는 결론이 된다.

⇒ P=NP인지, 아니면 P≠NP인지를 묻는 것이 바로 이 P-NP 문제이다.