P-NP 문제

위키백과 ― 우리 모두의 백과사전.

밀레니엄 문제
P-NP 문제
호지 추측
푸앵카레 추측
리만 가설
양-밀스 질량 간극 가설
나비에-스토크스 방정식
버츠와 스위너톤-다이어 추측

P-NP 문제PNP가 같은지에 대한 문제로, 미해결 상태이다.

컴퓨터가 답이 되는 몇가지 경우는 빠르게 찾을 수 있지만, 완벽한 답을 빠르게 찾을 수는 없는 모든 경우에 대한 문제이다. 이것은 전산학 이론에서 가장 중요한 미해결 문제이다.

P는 NP에 속하지만, NP가 P에 속하는지 여부는 밝혀지지 않았다.
P는 NP에 속하지만, NP가 P에 속하는지 여부는 밝혀지지 않았다.

[편집] 이야기

  • 2003년 12월 24일, 전북대학교 김양곤 교수는 리 대수를 이용하여 P≠NP 임을 증명하여 P-NP 문제를 해결했다고 주장했다. 그러나 학계에서는 실제로 문제를 해결한 것으로 인정하지 않고 있다.

[편집] 바깥고리

이 문서는 수학에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다.