PNP Problem

수학의미해결문제들 중의 하나.

모든 NP-class 문제는 P-class 문제로 변환될 수 있는가?

P(Polynomial-time)-class 문제란 TuringMachine으로 그 문제를 풀기 위한 알고리즘의 계산 횟수가 입력의 길이에 대해 다항식 함수로 제한되어 있는 문제를, 그리고 NP(nondeterministic polynomial-time)-class 문제는 아직 그 문제를 풀기 위한 계산 횟수가 다항식으로 제한된 알고리즘을 찾지 못한, 즉 아직 P-class임이 증명되지는 않았으나 어떤 답이 주어졌을 때에, 그 답이 맞는지 틀린지를 polynomial time에 증명할 수 있는 문제를 말한다. (이름이 암시하듯이 'nondeterministic TM 으로 다항식 시간에 풀 수 있는 문제'가 정의이다.)

P-class 문제의 가장 단순한 예로는 팩토리얼 함수가 있다. (See RecursiveFunction.) N!를 구하기 위해서는 단순히 1에서 N까지 곱하기 N번만 하면 되므로 이 알고리즘의 시간 복잡도는 O(N)이다. N은 N에 대한 다항식이므로 이 문제는 P-class 문제가 된다.

개중에는 O(N^2), O(N^3), 혹은 O(N^4)까지 되는 알고리즘도 있지만 이런 것 모두 P-class에 속하며, N이 커짐에 따라서 NP-class 문제에 비해 계산 시간이 많이 길어지지는 않는다.

TravelingSalesmanProblem은 NP-class 문제의 대표적인 예 중의 하나이다. TravelingSalesmanProblem은 한 세일즈맨이 각각 지점간의 거리가 주어진 N개의 도시들을 빠짐없이 방문하려고 할 때, 최단 경로를 찾는 문제이다.

이 문제를 푸는 가장 단순한 알고리즘은 세일즈맨이 다닐 수 있는 모든 경로를 탐색하는 것이다. N개의 도시를 순차적으로 방문하는 경우의 수는 N!이며 역순을 제외한다고 해도 N!/2이다. 게다가 각각의 경우에 대해서 거리를 계산(N번의 더하기)를 해야 하므로 이 방법의 시간복잡도는 O(N*N!)이 된다. (상수 부분은 떨어져 나간다) 이렇게 되면 N이 커질 수록 계산에 걸리는 시간이 말 그대로 기하급수적으로 증가하게 된다.

다른 NP-class 문제로는 "어떤 graph에서 length가 k보다 작은 hamiltonian cycle이 있는가?"가 있다.

수학자들은 이와 같은 NP-class 문제들을 P-class처럼 다항 시간 안에 풀 수 있게 되지 않을까... 하는 의문을 갖게 되었고 이것이 바로 PNPProblem의 시점이다.

최근에는 임의의 자연수가 소수인지의 여부를 판별해 내는 문제가 P-class 문제라는 사실이 밝혀졌다. see PrimalityTestIsP

김양곤 교수 100만달러짜리 수학난제 풀어
Linear Algebra, Lie Algebra and their applications to P versus NP
Reports on an alleged solution to the P vs NP problem: sci.math.research

좀 더 두고 봐야 할 것 같습니다. 갈수록 의심이 가는 것은 어쩔 수 없군요. --서상현
알고리즘 쪽을 전공하는 제 친구가 자신의 웹로그에 올린 글에는 "(논문의) Preprint를 읽어봤는데 논문의 저자가 P와 NP의 정의를 제대로 이해하고 있지 못한 듯 싶습니다"라고 써놨더군요. -- chung

뉴스메이커 기사: 한국 수학계가 이룬 쾌거인가, 아니면 어처구니없는 해프닝인가

Puzzlist의 홈페이지에 어느 분이 남긴 글
{{|
본 해프닝(?)의 개요는 다음과 같습니다.

1) 김양곤 교수는 중국의 전문대학 교수 그리고 성결대학교의 멀티미디어학부의 컴퓨터 그래픽전공의 교수인 진성아 교수와 함께 MATHPREPRINTS.COM에 문제의 논문 P!=NP를 게재합니다.

2) 위스콘신대학의 조교수인 남기봉 교수는 공동저자이기도 하고 아닌 것 같기도 합니다. 이름이 빠졌다가 넣어졌다가 하는데 아마 의견이 갈린 듯합니다. 남기봉 교수의 홈페이지의 C.V.에는 이것이 그냥 preprint로 넣어져 있습니다.

3) 어쨌든 본 논문은 미국의 두 SCI Journal에 투고가 되어졌다가 심사과정에서 오류가 지적되어 reject됩니다. 다시 중국의 SCI Journal에 투고했으나 결과는 마찬가지였습니다.

4) T. Chow 교수의 지적에 의하면 그들은 Lie Algebra의 전문가로 "non-deterministic coefficients", "deterministic coefficients"를 NP/P로 규정하고 그들의 machinery내에서 P이나 NP가 아닌 문제를 발견했다고 주장하지만, 이것은 더 강력한 machinery를 고려하지 않고 있으며 이에 대한 설명을 너무 모호하게 하고 있어서 증명이라 간주할 수 없다고 합니다.

5) 즉 그들은 P/NP의 전문가가 아니며 Lie Algebra의 전문가인데 이 분야를 연구하다가 유관성을 발견, 이의 해결을 시도하였으나 실패하였음에도 불구하고 계속 자신들의 주장을 (혹은 김양곤 교수의 주장)반복하고 있는 것입니다.

6) JAADS라는 인도의 잡지는 창간된 지 1년도 안된 잡지인데 현재 구독가능한 도서관이 저로서는 발견하기가 힘듭니다. 그런데 1년에 3번을 내는 잡지인데 작년에는 1년에 1번 나온 걸로 알고 있습니다. 그리고 김양곤 교수의 논문이 채택되기로 confirm된 것은 아닌 걸로 알고 있습니다.

7) 결론적으로 이 사건?은 한편의 해프닝으로 끝날 듯합니다. ^^;
|}}

수학분류 컴퓨터분류