우리가 보통 사용하는 컴퓨터에서 다항식 시간안에 해법을 찾을 수 있는 알고리즘이 있으면 P이고, 우리가 보통 사용하는 컴퓨터에서 누군가 답을 주면 그 답을 검증할 수 있는게 NP이다. 즉 P와 NP는 대응 관계가 아닌 NP안에 P도 들어가 있다. NP완전이란 NP중에 하나인데 다른 np문제를 np완전문제로 환원을 해서 np완전문제로 해결을 할 수가 있다. 그래서 np중에 가장 어려운문제가 np완전문제이다. 현재까지는 np완전문제를 다항식 시간안에 풀수없다고한다. (검증만 가능) 그렇기 때문에 np와 p는 같지 않다. p 는 다항식 시간안에 풀수 있음 걔는 NP 어떤문제는 다항식 시간안에 풀수 없다. 결정론적 튜링기계. 하지만 검증이 다항식 시간에 된다면 걔는 NP문제이다. 그래서 포함관계이다.