3 ms·
It's true that this is a really, really big theoretical advance, but it has almost zero impact on P vs NP. It's been believed for a long time that graph isomorp
by ColinWright 11y ago
It's true that this is a really, really big theoretical advance, but it has almost zero impact on P vs NP. It's been believed for a long time that graph isomorphism is "close to P" for some suitable definitions.
And this story has been discussion here on HN many many times over the past few weeks.
So this is a nice article about a seriously major breakthrough, but take all the P vs NP speculation with a huge handful of salt.
================
Discussions:
https://news.ycombinator.com/item?id=10731022 https://news.ycombinator.com/item?id=10731022 (75 comments)
Landmark Algorithm Breaks 30-Year Impasse (quantamagazine.org)
https://news.ycombinator.com/item?id=10505231 https://news.ycombinator.com/item?id=10505231 (41 comments)
Quasi-Polynomial Algorithm for Graph Isomorphism (scottaaronson.com)
https://news.ycombinator.com/item?id=10553879 https://news.ycombinator.com/item?id=10553879 (33 comments)
A Quasipolynomial Time Algorithm for Graph Isomorphism: The Details (jeremykun.com)
https://news.ycombinator.com/item?id=10610361 https://news.ycombinator.com/item?id=10610361 (3 comments)
A Little More on the Graph Isomorphism Algorithm (rjlipton.wordpress.com)
================
Here are some of the other submissions:
https://news.ycombinator.com/item?id=10504883 https://news.ycombinator.com/item?id=10504883
Graph Isomorphism in Quasi Polynominal Time
(calendar.google.com)
https://news.ycombinator.com/item?id=10506476 https://news.ycombinator.com/item?id=10506476
Graph Isomorphism in Quasi-polynomial time
(uchicago.edu)
https://news.ycombinator.com/item?id=10508418 https://news.ycombinator.com/item?id=10508418
Laci Babai and Graph Isomorphism
(lucatrevisan.wordpress.com)
https://news.ycombinator.com/item?id=10512074 https://news.ycombinator.com/item?id=10512074
A Big Result On Graph Isomorphism
(rjlipton.wordpress.com)
https://news.ycombinator.com/item?id=10542464 https://news.ycombinator.com/item?id=10542464
The world's fastest isomorphism testing
program (1993) (stonybrook.edu)
https://news.ycombinator.com/item?id=10547501 https://news.ycombinator.com/item?id=10547501
Summary of Babai's Breakthrough on Graph
Isomorphism (reddit.com)
https://news.ycombinator.com/item?id=10547881 https://news.ycombinator.com/item?id=10547881
Babai's Breakthrough on Graph Isomorphism
(reddit.com)
https://news.ycombinator.com/item?id=10553139 https://news.ycombinator.com/item?id=10553139
New algorithm efficiently solves graph isomorphism
problem (sciencenews.org)
https://news.ycombinator.com/item?id=10553152 https://news.ycombinator.com/item?id=10553152
Graph Isomorphism in Quasipolynomial Time
(uchicago.edu)
https://news.ycombinator.com/item?id=10562857 https://news.ycombinator.com/item?id=10562857
Solution to graph isomorphism problem found,
improves understanding of P and NP (sciencenews.org)
https://news.ycombinator.com/item?id=10565125 https://news.ycombinator.com/item?id=10565125
Claimed breakthrough in graph isomorphism
algorithm (technologyreview.com)
https://news.ycombinator.com/item?id=10601316 https://news.ycombinator.com/item?id=10601316
Graph Isomorphism in Quasipolynomial Time I [video]
(uchicago.edu)
https://news.ycombinator.com/item?id=10634234 https://news.ycombinator.com/item?id=10634234
László Babai Claims Quasipolynomial Algorithm
for Graph Isomorphism (aperiodical.com)
https://news.ycombinator.com/item?id=10687741 https://news.ycombinator.com/item?id=10687741
Laszlo Babai's Talk on His Quasipolynomial
Time Algorithm for Graph Isomorphism (uchicago.edu)
https://news.ycombinator.com/item?id=10729128 https://news.ycombinator.com/item?id=10729128
Graph Isomorphism in Quasipolynomial Time
(Babai's Preprint) (arxiv.org)
https://news.ycombinator.com/item?id=10730670 https://news.ycombinator.com/item?id=10730670
Graph Isomorphism in Quasipolynomial Time
(arxiv.org)
https://news.ycombinator.com/item?id=10735861 https://news.ycombinator.com/item?id=10735861
Graph isomorphism is quasi-polynomial time
by Laci Babai (arxiv.org)
https://news.ycombinator.com/item?id=10737655 https://news.ycombinator.com/item?id=10737655
Algorithm Solves Graph Isomorphism in Record
Time (quantamagazine.org)
https://news.ycombinator.com/item?id=10786874 https://news.ycombinator.com/item?id=10786874
Graph Isomorphism in Quasipolynomial Time
(arxiv.org)
- DrScump 11y agoThank you for spending so much time on this and other reference-cleanup and dupe-cleanup efforts; it can be a pretty thankless job in my experience.