❓

NP 복잡도

NP = Non-deterministic Polymial time

: 비 결정론적 튜링기계(NTM)으로 다항 시간 안에 풀 수 있는 판정 문제의 집합 ( 역도 성립 )

•

결정론적 튜링기계로 다항 시간에 풀 수 있는 문제는 비결정론적 튜링기계로도 다항 시간 안에 풀 수 있으므로 P집합 = NP집합의 부분집합
(단, P가 NP의 진부분집합(Proper subset)인지, P=NP인지는 알려지지 않음. P-NP문제로 불리는 컴퓨터과학 분야의 대표적 미해결 문제 이다.)