7. P / NP

P / NP 문제(polynomial Time-다항시간, Nondeterministic polynomial Time-결정되지않은 다항시간)

아래그림

•이때 “답안”이 주어졌을때 정답인지 아닌지 쉽게 (다항 시간에) 판단할 수 있는 문제들의 집합을 NP라 하고

•실제로 “정답”을 다항 시간에 만들어 낼 수 있는 알고리즘이 알려진 문제들을 P 라고 함

 

•따라서, P는 NP 집합의 부분집합임