P-NP 문제
위키백과 ― 우리 모두의 백과사전.
밀레니엄 문제 |
---|
P-NP 문제 |
호지 추측 |
푸앵카레 추측 |
리만 가설 |
양-밀스 질량 간극 가설 |
내비어-스톡스 방정식 |
버츠와 스위너톤-다이어 추측 |
P-NP 문제는 P와 NP가 같은지에 대한 문제로, 미해결 상태이다.
컴퓨터가 답이 되는 몇가지 경우는 빠르게 찾을 수 있지만, 완벽한 답을 빠르게 찾을 수는 없는 모든 경우들에 대한 문제이다. 이것은 전산학 이론에 있어 가장 중요한 미해결 문제이다.
[편집] 이야기
- 2003년 12월 24일, 전북대학교 김양곤 교수는 리 대수를 이용하여 P≠NP 임을 증명하여 P-NP 문제를 해결했다고 주장했다. 그러나 학계에서는 실제로 문제를 해결한 것으로 인정하지 않고 있다.
[편집] 바깥고리
- 길거리의 행인을 위한 백만불 현상 문제 소개: P = NP? - 서울대학교 수학과 김홍종 교수
분류: 밀레니엄 문제 | 복잡도 종류 | 수학의 미해결 문제 | 전산학의 미해결 문제 | 추측