P-NP 문제

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

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

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

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

P는 NP에 속하지만, NP가 P에 속하는지 여부는 밝혀지지 않았다.
실제 크기로
P는 NP에 속하지만, NP가 P에 속하는지 여부는 밝혀지지 않았다.

[편집] 이야기

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

[편집] 바깥고리