P-NP 문제: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
Singleheart (토론 | 기여) |
P-NP 문제가 처음으로 제안된 내용, 같이 보기 추가 |
||
2번째 줄:
[[파일:Complexity classes.png|thumb|P는 NP에 속하지만, NP가 P에 속하는지 여부는 밝혀지지 않았다.]]
'''P-NP 문제'''는 [[복잡도 종류]] [[P (복잡도)|P]]와 [[NP (복잡도)|NP]]가 같은지에 대한 [[컴퓨터 과학]]의 미해결 문제로, [[1971년]] [[스티븐 쿡]]이 처음으로 제안하였고 [[클레이 수학연구소]]에서 발표한 7개의 '밀레니엄 문제' 중 하나이며 컴퓨터 과학에서 중요한 위치를 차지하고 있다.
P는 [[결정론적 튜링 기계]]를 사용해 [[다항 시간]] 내에 답을 구할 수 있는 문제의 집합이고, NP는 [[비결정론적 튜링 기계]]를 사용해 다항 시간 내에 답을 구할 수 있는 문제의 집합이다. 여기에서 결정론적 튜링 기계에 사용한 프로그램을 비결정론적 튜링 기계에 적용할 수 있으므로, P는 NP의 부분집합이 된다. 하지만 여기에서 P와 NP가 같은 집합인지, 아니면 P가 NP의 [[진부분집합]]인지는 아직 밝혀지지 않았다. 현재 2000년에 클레이 수학연구소가 100만 달러를 걸었다.
18번째 줄:
== 참고 사항 ==
* [[2003년]] [[12월 24일]], [[전북대학교]] [[김양곤]] 교수는 [[리 대수]]를 이용하여 P≠NP 임을 증명하여 P-NP 문제를 해결했다고 주장했다. 그러나 학계에서 인정받지는 못했다. 이들은 어떤 문제가 [[다항 시간]]에 풀리지 않는 것을 증명하였는데, 그 문제가 [[NP (복잡도)|NP]]에 속함이 증명되지 않았기 때문에, P-NP 문제의 증명으로 볼 수 없기 때문이다.
== 같이 보기 ==
* [[수학의 미해결 문제]]
* [[컴퓨터 과학의 미해결 문제]]
* [[게임 복잡도]]
== 주석 ==
|