구독상품안내
꼭짓점과 꼭짓점을 잇는 변으로 이뤄진 대상을 ‘그래프’라고 합니다. 그래프는 ({1,2,3}, {1-2,2-3, 3-1})처럼 꼭짓점 집합과 변 집합의 순서쌍으로 나타냅니다. 매우 추상적이지요. 지하철 노선도처럼 꼭짓점은 점, 두 꼭짓점을 잇는 변은 선으로 나타낸 그림이라고 생각하면 간단합니다.
위의 두 그래프는 전혀 달라 보이지만 꼭짓점을 잘 옮기면 같은 그래프가 됩니다. 수학에서는 이런 두 그래프가 ‘동형 관계’에 있다고 합니다. 즉 그래프 동형 문제는 두 그래프가 동형 관계에 있는지 묻는 것입니다.
그런데 꼭짓점이 10개인 그래프의 경우 꼭짓점의 자리를 바꿔놓는 방법이 무려
10!=10×9×8×7×6×5×4×3×2×1=3,628,800가지나 됩니다. 꼭짓점이 n개라면 그 수는 n!이 되겠지요. 꼭짓점이 n개인 두 그래프가 동형 관계인지 확인하기 위해서는 첫 번째 그래프에서 꼭짓점의 자리를 바꾸는 모든 경우의 수인 n!가지를 다 해보고, 그 중에서 두 번째 그래프와 똑같은 것이 나오는지 따져봐야 합니다.
그런데 n!가지 경우를 다 확인하지 않고도 답을 구할 수 있습니다. 두 그래프의 변의 수가 다르다거나, 꼭짓점의 수가 다르다면 두 그래프가 절대 같을 수 없다는 것을 바로 알 수 있으니까요. 예를 들어 꼭짓점 10개짜리 그래프인데 변이 3개씩 연결된 꼭짓점이 5개, 4개씩 연결된 꼭짓점이 5개 있다면, 10! 대신 5!×5!=14,400가지 경우만 따져도 되는 것이지요.
진전은 없었습니다. 그런데 지난해 11월 바바이 교수가 어떤 상수 C와 d에 대해 2C (log n)d번 안에 반드시 정답을 말할 수 있는 알고리듬을 만들었다고 주장한 것입니다. 만일 d=1이라면 2C (log n) =nc이므로 바로 n에 관한 다항식이 됩니다. 비록 d=1이라고 증명한 것은 아니지만 1보다 큰 어떤 상수라도 기존 결과를 훨씬 뛰어넘는 매우 놀라운 결과가 됩니다. 논문은 인터넷에 공개됐지만 전문가의 검토를 거친 것이 아니므로 좀 더 기다려봐야겠지만요.
밀레니엄 난제, P VS NP
2000년 클레이 수학재단에서는 수학의 어려운 미해결 문제 7개를 뽑아 발표하면서 그 중 어떤 문제든 푼 사람에게는 100만 달러(한화 11억 5630만 원)를 상금으로 주겠다고 발표했습니다. 그 중 하나가 P≠NP인지 P=NP인지 증명하라는 문제입니다. P가 특정한 횟수 안에 풀 수 있는 문제의 집합이라면, ‘NP’는 문제의 풀이과정을 보고 그 문제의 답이 맞는지 특정한 횟수 안에 확인할 수 있는 문제의 집합을 말합니다. 문제를 풀기는 어렵지만, 그 풀이과정이 맞는지 확인하는 건 그보다 쉽습니다. 눈치 빠른 독자라면 알겠지만 P는 NP에 속합니다.
만일 P=NP라면 특정한 횟수 안에 풀이를 검증할 수 있는 모든 문제는 특정한 횟수 안에 문제를 풀 수 있습니다. 그런데 대부분의 학자들은 P≠NP라고 생각하고 있습니다. 실제로 P≠NP라고 가정했을 때 어떤 문제를 푸는 효율적인 알고리듬은 존재하지 않는다는 걸 증명한 논문이 많이 있습니다.
밀레니엄 난제, P VS NP
2000년 클레이 수학재단에서는 수학의 어려운 미해결 문제 7개를 뽑아 발표하면서 그 중 어떤 문제든 푼 사람에게는 100만 달러(한화 11억 5630만 원)를 상금으로 주겠다고 발표했습니다. 그 중 하나가 P≠NP인지 P=NP인지 증명하라는 문제입니다. P가 특정한 횟수 안에 풀 수 있는 문제의 집합이라면, ‘NP’는 문제의 풀이과정을 보고 그 문제의 답이 맞는지 특정한 횟수 안에 확인할 수 있는 문제의 집합을 말합니다. 문제를 풀기는 어렵지만, 그 풀이과정이 맞는지 확인하는 건 그보다 쉽습니다. 눈치 빠른 독자라면 알겠지만 P는 NP에 속합니다.
만일 P=NP라면 특정한 횟수 안에 풀이를 검증할 수 있는 모든 문제는 특정한 횟수 안에 문제를 풀 수 있습니다. 그런데 대부분의 학자들은 P≠NP라고 생각하고 있습니다. 실제로 P≠NP라고 가정했을 때 어떤 문제를 푸는 효율적인 알고리듬은 존재하지 않는다는 걸 증명한 논문이 많이 있습니다.
NP 문제 중에 이 문제를 풀면 다른 NP 문제 모두를 특정한 횟수 내에 풀 수 있다고 증명된 것이 있습니다. 이를 ‘NP-완전’ 문제라고 합니다. 어떤 논리식이 참이 되게 할 수 있는지 물어보는 문제가 가장 먼저 증명된 NP-완전 문제입니다. 이는 1971년에 미국의 전산학자 스티븐 쿡이 증명해 ‘쿡의 정리’라고 널리 알려져 있습니다. 소련의 전산학자 레노이드 레빈도 그 사실을 모르고 독자적으로 증명해 지금은 ‘쿡-레빈 정리’라고도 부릅니다.
지금은 NP-완전 문제로 증명된 문제가 많습니다. NP-완전인 문제 중 어느 하나라도 P에 들어가는 것이 증명된다면 P=NP가 됩니다. 하지만 NP-완전인 문제는 아마도 P에 들어가지 않을 것으로 추측됩니다.
많은 사람들이 그래프 동형 문제는 NP-완전이 아닐 거라고 추측했습니다. 룩스 교수의 기존 알고리듬이 지금까지 알려진 NP-완전의 그 어떤 문제보다 빠른 시간 안에 풀 수 있기 때문입니다.
그래프 동형 문제, P가 될 수 있을까?
이번 바바이 교수의 증명이 맞다면 그래프 동형 문제는 생각보다 P에 매우 가까워지는 셈입니다. 예전에도 그런 일이 있었습니다. 어떤 수가 소수인지아닌지 판별하는 문제는 한동안 NP문제이면서 P인지 아닌지 몰랐습니다. 한참 동안 P에 매우 가까운 알고리듬만 알려져 있었지요.
그런데 2002년 인도 칸쿠르 공과대학에 갓 입학한 두 학생 니라지 카얄과 니틴 삭세나, 그 지도교수 마닌드라 아그라왈이 n자리 자연수가 소수인지 아닌지 어떤 상수 C에 대해 Cn12번 안에 알 수 있다는 것을 증명해 세상을 깜짝 놀라게 했습니다.
과연 그래프 동형 문제가 소수 판별 문제처럼 몇십 년 뒤에 P에 들어가게 될까요? 그 답을 하루 빨리 알 수 있는 날이 왔으면 좋겠습니다.
지금은 NP-완전 문제로 증명된 문제가 많습니다. NP-완전인 문제 중 어느 하나라도 P에 들어가는 것이 증명된다면 P=NP가 됩니다. 하지만 NP-완전인 문제는 아마도 P에 들어가지 않을 것으로 추측됩니다.
많은 사람들이 그래프 동형 문제는 NP-완전이 아닐 거라고 추측했습니다. 룩스 교수의 기존 알고리듬이 지금까지 알려진 NP-완전의 그 어떤 문제보다 빠른 시간 안에 풀 수 있기 때문입니다.
그래프 동형 문제, P가 될 수 있을까?
이번 바바이 교수의 증명이 맞다면 그래프 동형 문제는 생각보다 P에 매우 가까워지는 셈입니다. 예전에도 그런 일이 있었습니다. 어떤 수가 소수인지아닌지 판별하는 문제는 한동안 NP문제이면서 P인지 아닌지 몰랐습니다. 한참 동안 P에 매우 가까운 알고리듬만 알려져 있었지요.
그런데 2002년 인도 칸쿠르 공과대학에 갓 입학한 두 학생 니라지 카얄과 니틴 삭세나, 그 지도교수 마닌드라 아그라왈이 n자리 자연수가 소수인지 아닌지 어떤 상수 C에 대해 Cn12번 안에 알 수 있다는 것을 증명해 세상을 깜짝 놀라게 했습니다.
과연 그래프 동형 문제가 소수 판별 문제처럼 몇십 년 뒤에 P에 들어가게 될까요? 그 답을 하루 빨리 알 수 있는 날이 왔으면 좋겠습니다.
일러스트 : 뻐가콜라
