P-NP 문제
위키백과 ― 우리 모두의 백과사전.
| 밀레니엄 문제 |
|---|
P-NP 문제는 복잡도 종류 P와 NP가 같은지에 대한 미해결 문제로, 클레이 수학연구소에서 발표한 7개의 '밀레니엄 문제' 중 하나이며 컴퓨터 과학에서 중요한 위치를 차지하고 있다.
P는 결정론적 튜링 기계를 사용해 다항 시간 내에 답을 구할 수 있는 문제의 집합이고, NP는 비결정론적 튜링 기계를 사용해 다항 시간 내에 답을 구할 수 있는 문제의 집합이다. 여기에서 결정론적 튜링 기계에 사용한 프로그램을 비결정론적 튜링 기계에 적용할 수 있으므로, P는 NP의 부분집합이 된다. 하지만 여기에서 P와 NP가 같은 집합인지, 아니면 P가 NP의 진부분집합인지는 아직 밝혀지지 않았다. 현재 2000년에 클레이 수학연구소가 100만 달러를 걸었다.
목차 |
[편집] 예상
2002년에 100명을 대상으로 한 설문조사에서, 61명이 P와 NP가 다를 것이라고 답했고 9명은 같을 것이라고 답했다.[1]
[편집] NP-완전
- 이 부분의 본문은 NP-완전입니다.
NP-완전 문제는 NP에 속하는 문제 중에서 가장 어려운 문제로 생각할 수 있는데, 어떤 NP에 속하는 문제가 있어서 NP에 있는 모든 문제를 다항 시간 내에 그 문제로 변환할 수 있다면 이 문제는 NP-완전에 속한다.
이 집합이 중요한 이유는, NP-완전에 속하는 문제 중 하나라도 P에 속한다는 것을 밝힌다면 P=NP를 증명할 수 있기 때문이다.
[편집] 참고 사항
- 2003년 12월 24일, 전북대학교 김양곤 교수는 리 대수를 이용하여 P≠NP 임을 증명하여 P-NP 문제를 해결했다고 주장했다. 그러나 학계에서는 실제로 문제를 해결한 것으로 인정하지 않고 있다.
[편집] 주석
[편집] 바깥 고리
- 길거리의 행인을 위한 백만불 현상 문제 소개: P = NP? - 서울대학교 수학과 김홍종 교수
 |
이 글은 전산학에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다. |
