행렬 곱 알고리즘의 복잡도

가급적 한쪽 분야로 치우치지 않고 싶은데, 자꾸 복잡도 이론과 관련해서 포스팅하게 되네 이거-_-

간만에 Luca Trevisan 선생의 블로그 in theory[1]를 보니 뭔가 수상한(?) 논문[2]을 소개하고 있다.

matrix multiplication의 알고리즘 속도가 \Theta(n^2 )라고 주장하는 내용인 듯 한데, Ran Raz의 증명[3]에 의하면 matrix multiplication의 속도는 \Theta(n^2 \log n)이하로 내려갈 수 없다고 한다. 헐 이게 어떻게 된 일이야?

어쨌든 Luca 선생은 Scott Aaronson 선생의 “수학적 사기꾼을 구별하는 열가지 증거”[4]에서 4번에 걸린다는 이야기를 한다. 일전에 graph isomorphism 사건[5]도 있었지만, 저자가 논문을 철회했다면 뭐 좀 실수할 수도 있는 거지-_- 사기꾼 이야기하는 건 좀 아닌 것 같습니다. 허허허

 


2017.3.30
[2]의 논문이 오늘 보니 제목이 바뀌어 있다. 저자가 오류를 고친 듯. ㅎㅎㅎ

 


[1] Matrix Multiplication Not Yet Doable In Quadratic Time in in theory
[2] Yijie Han, (2016) “A \theta(n^2 ) Time Matrix Multiplication Algorithm”, arXiv:1612.04208 [cs.DS]
[3] Ran Raz, (2002) “On the complexity of matrix product”, Society for Industrial and Applied Mathematics Journal on Computing, 32(5), 1356–1369. (14 pages), doi:10.1137/S0097539702402147
[4] 내 백과사전 수학적 사기꾼을 구별하는 열가지 증거 2011년 12월 16일
[5] 내 백과사전 graph isomorphism 판정 알고리즘의 철회 2017년 1월 6일

Advertisements

답글 남기기

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

WordPress.com 로고

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

Twitter 사진

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

Facebook 사진

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

Google+ photo

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

%s에 연결하는 중