그래프 동형 문제

그래프 동형 문제는 두 그래프가 동형 관계에 있는지 묻는 것이다. 2015년 새로운 연구 결과가 등장하여 그래프 동형 문제가 P 문제에 속하는지에 대해 관심이 증폭되고 있다.

2015년 11월, 미국 시카고대에서 열린 세미나 하나가 전세계 수학자와 컴퓨터과학자의 이목을 집중시켰습니다. 시카고대의 라슬로 바바이 교수가 어떤 두 그래프가 같은지 다른지 따지는 알고리듬을 주제로 강연했는데, 그 알고리듬이 이제까지 알려진 어느 알고리듬보다 빨랐기 때문입니다. 대체 어떤 의미인지 지금부터 자세히 알아봅시다.

꼭짓점과 꼭짓점을 잇는 변으로 이뤄진 대상을 ‘그래프’라고 합니다. 그래프는 ({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가지 경우만 따져도 되는 것이지요.

정해진 단계 안에 풀리면 P 문제

특정한 횟수 안에 ‘예’ 또는 ‘아니오’라고 정확하게 답할 수 있는 문제의 집합을 ‘P’라고 합니다. 더 정확하게 말하면 영국의 수학자 앨런 튜링이 1936년에 만든 개념인 튜링기계에 N개의 글자를 입력하면 처럼 특정한 횟수만큼 동작을 하고 나서 ‘예’ 또는 ‘아니오’라고 대답할 수 있는 문제를 말하지요.

예를 들어 1, 2, 3, 4라는 수열을 4, 3, 2, 1로 순서를 바꾸는 알고리듬이 있습니다. 이 알고리듬은 두 수를 비교해서 더 큰 수가 앞에 오도록 두 수의 위치를 바꿉니다. 그러면 아래와 같은 단계를 거칩니다.

총 3+2+1=6번 만에 1, 2, 3, 4를 4, 3, 2, 1로 다시 배열합니다. 만약 수열의 길이가 4가 아니라 n이라면 얼마나 걸릴까요? 다음과 같이 됩니다.

즉 이것은 n에 관한 다항식 번 안에 문제를 풀게 되지요.

최근까지 그래프 동형 문제에 관한 가장 빠른 알고리듬은 1983년 미국 오레곤대 유진 룩스 교수가 발표한 것입니다. 룩스 교수의 알고리듬은 꼭짓점이 n개인 그래프의 경우 어떤 상수 C에 대해  번 안에 반드시 정답을 말합니다. 이 다항식은 n에 관한 다항식이 아니기 때문에 P문제라고 말할 수가 없습니다. 지난 30여 년 동안 더 이상의 진전은 없었습니다.

그런데 2015년 11월 바바이 교수가 어떤 상수 C와 d에 대해

번 안에 반드시 정답을 말할 수 있는 알고리듬을 만들었다고 주장한 것입니다. 만일 d=1이라면

이므로 바로 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 문제인 것이 증명될 수 있을까?

NP 문제 중에 이 문제를 풀면 다른 NP 문제 모두를 특정한 횟수 내에 풀 수 있다고 증명된 것이 있습니다. 이를 ‘NP-완전’ 문제라고 합니다. 어떤 논리식이 참이 되게 할 수 있는지 물어보는 문제가 가장 먼저 증명된 NP-완전 문제입니다. 이는 1971년에 미국의 전산학자 스티븐 쿡이 증명해 ‘쿡의 정리’라고 널리 알려져 있습니다. 소련의 전산학자 레노이드 레빈도 그 사실을 모르고 독자적으로 증명해 지금은 ‘쿡-레빈 정리’라고도 부릅니다.

지금은 NP-완전 문제로 증명된 문제가 많습니다. NP-완전인 문제 중 어느 하나라도 P에 들어가는 것이 증명된다면 P=NP가 됩니다. 하지만 NP-완전인 문제는 아마도 P에 들어가지 않을 것으로 추측됩니다.

많은 사람들이 그래프 동형 문제는 NP-완전이 아닐 거라고 추측했습니다. 룩스 교수의 기존 알고리듬이 지금까지 알려진 NP-완전의 그 어떤 문제보다 빠른 시간 안에 풀 수 있기 때문입니다.

그래프 동형 문제, P가 될 수 있을까?

이번 바바이 교수의 증명이 맞다면 그래프 동형 문제는 생각보다 P에 매우 가까워지는 셈입니다. 예전에도 그런 일이 있었습니다. 어떤 수가 소수인지 아닌지 판별하는 문제는 한동안 NP문제이면서 P인지 아닌지 몰랐습니다. 한참 동안 P에 매우 가까운 알고리듬만 알려져 있었지요.

그런데 2002년 인도 칸쿠르 공과대학에 갓 입학한 두 학생 니라지 카얄과 니틴 삭세나, 그 지도교수 마닌드라 아그라왈이 n자리 자연수가 소수인지 아닌지 어떤 상수 C에 대해 번 안에 알 수 있다는 것을 증명해 세상을 깜짝 놀라게 했습니다.

과연 그래프 동형 문제가 소수 판별 문제처럼 몇 십 년 뒤에 P에 들어가게 될까요? 그 답을 하루 빨리 알 수 있는 날이 왔으면 좋겠습니다.

동아사이언스