graph isomorphism 판정 알고리즘의 철회

일전에 graph isomorphism 판정을 quasipolynomial로 하는 알고리즘을 발견했다는 이야기[1]를 했는데, 그 내용에 오류가 있어서 논문[2]이 철회된 것 같다. 타오 선생도 언급[3]하고 있고, Quanta magazine 기사[4]로도 나왔다. 팀 블로그인 Windows on Theory[5]와 Gödel’s Lost Letter and P=NP[6]에서도 이 내용을 언급하고 있다.

그러나 quasipolynomial은 아니지만 여전히 sub-exponential이고 기존에 알려진 어떤 알고리즘보다 빠른 것이라고 한다. 음… 혹시나 알고리즘이 점점 개선되어 결국 P=NP가 되지 않을까 가슴 두근하던 나의 망상을 확 깨주시는군-_-

논문[2]의 중요한 오류 부분을 Harald Helfgott 선생이 지적한 모양인데, 이 사람 약한 골드바흐 추측을 끝장낸[7] 바로 그 페루 출신 수학자가 아닌가. 이쪽 분야로도 소양이 있는 줄은 몰랐네 ㅋ

Helfgott 선생의 블로그[8]를 보니 2014년 ICM 때문에 한국에 다녀간 모양인데, 한글의 창제 원리에 대해 꽤 흥미로워 하는 듯? 근데 ‘아침글’이라는 표현은 처음 듣는데, 내가 뭔가 잘못알고 있는 건지…-_- 국어 선생님에게 물어봐야겠다. ㅋ

여하간 Helfgott 선생은 한국의 로컬푸드와 주류는 가격이 싼데, 커피는 비싼 점이 미스테리라고 생각하는 것 같다. ㅎㅎㅎ

 


2017.1.15
Quanta magazine Graph Isomorphism Vanquished — Again January 14, 2017
Babai 선생이 증명을 다시 고쳐서 quasipolynomial이 된 듯 하다. ㅋ

 


[1] 내 백과사전 새로운 graph isomorphism 판정 알고리즘 2015년 11월 14일
[2] László Babai (2015) “Graph Isomorphism in Quasipolynomial Time”, arXiv:1512.03547 [cs.DS]
[3] https://plus.google.com/+TerenceTao27/posts/2nSqird8NHt?sfc=true
[4] Quanta magazine Complexity Theory Problem Strikes Back January 5, 2017
[5] On exp(exp(sqrt(log n))) algorithms. in Windows on Theory
[6] Babai’s Result: Still a Breakthrough in Gödel’s Lost Letter and P=NP
[7] 내 백과사전 홀수 골드바흐 추측이 완전히 풀렸나? 2013년 5월 14일
[8] Hangul and stinky tofu in The value of the variable

Advertisements

2 thoughts on “graph isomorphism 판정 알고리즘의 철회

  1. 저도 최근에 이 논문의 소식들에 관심이 있고 포스팅할까 고민하고 있었는데! 이 논문이 다시 Quasi-poly라고 고쳐졌다고 하더라구요.

    Quantum computation쪽에서 비슷하게 breakthrough가 있었는데, 정확하게는 기억이 안나지만 randomized NP-hard수준의 어떤 문제중 일부케이스(제가 정확히 읽은 것이 아니라 정확하게는 모르겠네요)를 quantum polytime에 풀 수 있다는 논문 (https://arxiv.org/abs/1611.06999)이 있었는데요, 이 논문도 miscalculation으로 철회가 되고 이 논문의 경우는 아쉽게도 개선되지 않는 것 같네요. 조금 더 자세히 알게되면 제가 한번 포스팅을 ㅎㅎ

답글 남기기

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

WordPress.com 로고

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

Twitter 사진

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

Facebook 사진

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

Google+ photo

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

%s에 연결하는 중