GI is quasi-polynomial time solvable.

10 views

Skip to first unread message

Đức Hoàng Anh

unread,

Dec 14, 2015, 8:08:13 PM12/14/15

to Groupmail Toán TT

László Babai is one of the world experts on complexity theory, especially related to groups and graphs. He also recently won the 2015 ACM Knuth Prize, for which we congratulate him.

He has announced that will place graph isomorphism almost in polynomial time.

More exactly László shows that Graph Isomorphism is in Quasipolynomial Time: that is time of the form

$\displaystyle 2^{O(\log(n))^{c}},$

for some constant ${c}$ . Polynomial time is the case when ${c=1}$ , but any ${c}$ is a huge improvement over the previous best result.

http://arxiv.org/abs/1512.03547

Best regards.

Hoàng Anh Đức.

(K53 Advanced Math, HUS, 2008-2012)

Sent from my iPhone.

Reply all

Reply to author

Forward

0 new messages