P-NP 문제: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
진실수정 |
내용수정 |
||
2번째 줄:
[[파일:Complexity classes.png|섬네일|P는 NP에 속하지만, NP가 P에 속하지않는다는 사실이 밝혀졌다.]]
'''P-NP 문제'''는 [[복잡도 종류]] [[P (복잡도)|P]]와 [[NP (복잡도)|NP]]가 같은지에 대한 [[컴퓨터 과학]]의 미해결
P는 [[결정론적 튜링 기계]]를 사용해 [[다항 시간]] 내에 답을 구할 수 있는 문제의 집합이고, NP는 [[비결정론적 튜링 기계]]를 사용해 다항 시간 내에 답을 구할 수 있는 문제의 집합이다. 여기에서 결정론적 튜링 기계에 사용한 프로그램을 비결정론적 튜링 기계에 적용할 수 있으므로, P는 NP의 부분집합이 된다.
|