News for hackers. Stuff that matters.
Re:Complex problem made simple sends computer scientists wild by WalterSear on Wednesday November 11, 2015 @02:11PM (#10548544)
Babai declined to be interviewed about the work, saying it must first stand up to the scrutiny of peer review. “I understand that in the internet age, even a simple seminar announcement can trigger an explosion in the blogosphere, but this is no reason to compromise the process,” he says. “The reaction of colleagues at this point is not celebration but anticipation. The results need to be verified by the research community.

I say, bravo.

Re:Complex problem made simple sends computer scientists wild by notacoward on Thursday November 12, 2015 @11:08AM (#10553974)
I came here to say the same thing, but you beat me to it. It's awesome that Babai has used this moment in the spotlight to deliver a message about respect for the scientific process. What class.
Re:Complex problem made simple sends computer scientists wild by 0xdeadbeefbabe on Thursday November 12, 2015 @11:46AM (#10554241)
> Babai’s new result says that solving graph isomorphism takes slightly longer than polynomial time – not quite placing it in P, but significantly shifting the needle for the first time.

What is the needle and how did it shift significantly for the first time?

Edit: They already knew it was in NP, but now they know it is not in P (or not quite in P)?

Re:Complex problem made simple sends computer scientists wild by poizan42 on Friday November 13, 2015 @03:07AM (#10558566)
If it was proven that it's not in P then we would have shown that P!=NP which would be HUGE.

No, this is "merely" finding a more efficient algorithm for a problem which we still don't know exactly where belongs. From a complexity theoretical viewpoint nothing is changed. It's still possible that graph isomorphism is in P.

Now if graph isomorphism is shown to be NP-complete then this result would imply that every problem in NP can be solved in sub-exponential time which would have huge practical consequences.

Re:Complex problem made simple sends computer scientists wild by andreasvc on Thursday November 12, 2015 @11:55AM (#10554321)
All of P is in NP. The result claims that it is close to P, when before it was probably expected to be much harder than P.
Re:Complex problem made simple sends computer scientists wild by i573323 on Thursday November 12, 2015 @10:40AM (#10553758)
Now THAT's a clickbaitey title.
Re:Complex problem made simple sends computer scientists wild by uremog on Thursday November 12, 2015 @04:33PM (#10556304)
What these Computer Scientists do next will amaze you!
Re:Complex problem made simple sends computer scientists wild by intrasight on Thursday November 12, 2015 @11:02AM (#10553938)
And it worked - I clicked it
Re:Complex problem made simple sends computer scientists wild by brianclements on Thursday November 12, 2015 @02:53PM (#10555639)
I agree too, if I was allowed to editorialize I would have sterilized it.