새로운 graph isomorphism 판정 알고리즘

본인도 복잡도 이론에 대해 문외한이므로 본 블로그 설명은 틀릴 수 있다. 걍 대충 위키피디아 읽어보고-_- 글쓰고 있으니 참고하시라. ㅋㅋ

decision problem이란 주어진 질문에 yes 또는 no로 답할 수 있는 문제를 말한다.

P는 deterministic Turing machine으로 다항식 시간에 풀 수 있는 decision problem들의 집합을 말한다. 걍 우리가 가진 컴퓨터로 다항식 시간에 풀 수 있는 문제인 것 같다.

NP는 Non-deterministic Turing machine으로 다항식 시간에 풀 수 있는 decision problem들의 집합을 말한다. 이 머신이 뭔진 몰라도 우리가 쓰는 컴퓨터보다 훨 쎈 머신 같다. ㅋ 정의상 P는 NP의 부분집합이 된다.

NP-hard는 다항식 시간내에 NP의 모든 문제로 변환 가능한 decision problem들의 집합을 말한다. 이름과는 달리 NP의 부분집합이 아니다.

NP-complete는 NP-hard와 NP의 교집합이다.

NP-intermediate는 NP중에서 P도 아니고 NP-complete도 아닌 decision problem들의 집합을 말한다.

복잡도를 비교하자면,

    P 문제는 문제의 답도 찾기 쉽고, 찾은 답이 맞는지 확인하기도 쉬운 문제.
    NP-intermediate 문제는 답은 찾기 어렵지만, 찾은 답이 맞는지 확인하기는 쉬운 문제.
    NP-hard는 답도 찾기 어렵고, 찾은 답이 맞는지 확인하기도 어려운 문제.

수제 맥주집 N개가 주어져 있다고 하자.

이 수제 맥주집들 중에 특정한 이곳이 가장 맛있는가? 라고 물으면 decision problem이다.

이를 풀려면 수제 맥주집들을 한 번씩 방문만 하면 되므로 데이터양 N에 비례하여 푸는 시간이 늘어난다. 따라서 P

이 수제 맥주집들을 모두 방문하는 총 길이 X이하의 경로가 존재하는가? 라고 물으면 decision problem이다.

이를 풀려면 수제 맥주집을 모두 방문하는 경로를 일일이 조사해야 하므로 데이터양 N에 대해 N!에 비례하여 푸는시간이 늘어난다. 그런데 X이하의 경로를 주면 확인하기는 쉽다. 따라서 NP-intermediate

이 수제 맥주집들을 모두 방문하는 가장 짧은 경로가 이것인가? 라고 물으면 decision problem이다.

이를 풀려면 데이터양 N에 대해 N!의 경로를 조사해야하고, 주어진 답이 맞는지도 즉시 알 수 없다. 따라서 NP-hard.

참고로 이런 삽질[1]을 하는 친구도 있더라. ㅋ

 


일전에 P!=NP문제가 풀렸나[2] 하며 소동이 일어나더니만 잠잠해졌는데-_- 다시 전산수학계에서 화제로 떠오르는 이야기가 나오고 있다. László Babai라는 수학자가 graph isomorphism 문제를 거의 다항식 시간에 푸는 알고리즘을 찾았다는 소문이다. 아직 논문으로는 내지 않았는데 벌써 화제가 되고 있는 걸 보면 꽤 큰 문제인 듯.

상당히 많은 NP문제들이 NP-complete로 분류되고 있기 때문에 NP-intermediate문제가 그리 흔하지는 않은 편인데, 실용적인 몇몇 문제가 이쪽으로 포진되어 있다. 예를 들어 정수의 소인수분해 문제나 discrete logarithm과 같은 문제인데, 암호학과 밀접한 연관이 있다. 뭐 아직 P=NP가 안 풀렸기 때문에 이 문제들이 모두 P일 가능성도 배제할 수는 없다.

graph isomorphism 문제도 NP-intermediate 문제들 중의 하나인데, 주어진 두 graph가 isomorphic한가? 라는 결정문제를 해결하는 문제이다. 이 문제는 SNS에서 사회 관계망 분석이나 네트워크 등에서 써먹는 실용적인 용도가 있는 모양인 듯. 이와 관련해서 유명한 수학 블로거인 Jeremy Kun씨의 훌륭한 포스트[3]가 얼마전에 올라왔으니 참고 바란다. MIT Technology Review기사[4]도 있다.

여태까지 알려진 가장 빠른 알고리즘이 O \left(2^{\sqrt{n}\log n}\right)였던 모양인데, 요번에 발견된 것이 어떤 상수 c에 대해 O \left(2^{(\log n)^{c}}\right)라고 한다. 물론 c=1이면 즉시 P가 된다. 지수의 \sqrt{n}을 없앰으로서 지수적 증가부분을 없애고 다항식 시간에 근접했다는 것.

일전에 새로운 인수분해 알고리즘[5]이나 새로운 discrete logarithm 알고리즘[6] 이야기를 했지만 실용적인 측면에서도 NP-intermediate에 속하는 문제들이 꽤 위태로워 보인다. AKS와 같이 예상치 못한 것이 P에 속하는 수가 있기 때문에, 이 문제도 P로 판정날지도 모를 일이다. 이 문제들이 정말 P에 속한다면 꽤 큰 소동이 일 듯. ㅋㅋㅋ

 


[1] Top Brewery Road Trip, Routed Algorithmically in Flowing Data
[2] 내 백과사전 P != NP ?? 2010년 8월 10일
[3] A Quasipolynomial Time Algorithm for Graph Isomorphism: The Details in Math ∩ Programming
[4] MIT Technology Review Claimed Breakthrough Slays Classic Computing Problem; Encryption Could Be Next November 13, 2015
[5] 내 백과사전 새로운 인수분해 알고리즘 2014년 10월 24일
[6] 내 백과사전 RSA 암호는 깨질 것인가? 2013년 8월 11일

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중