3 ms·
Graph coloring problem is generic and is guaranteed to be useful in a myriad obvious applications. Plus, "polynomial time" is a specific criteria, whereas "some
by colllectorof 11y ago
Graph coloring problem is generic and is guaranteed to be useful in a myriad obvious applications. Plus, "polynomial time" is a specific criteria, whereas "somewhat better than a human champion" is an arbitrary milestone.
Besides, people who make advances in abstract problems like that do not release PR statements and get 1/1000th of the hype and coverage AlphaGo received recently.
- hluska 11y agoI'm not trying to troll you here, but have you ever actually played Go?? Go is so complex that the word 'complex' doesn't even begin to cover it. It's a game that requires equal parts creativity and logic. The sheer number of options absolutely dwarf anything else out there. This achievement will be useful in a myriad of obvious applications. And, it is one of the greatest engineering feats that I have been alive to witness.
- colllectorof 11y agoI have played Go and I understand that it is a complex and nuanced game. However, I also understand that it's a game very heavily based on patterns and pattern-matching. Have you read the research paper and seen how much of AlphaGo's architecture was designed around the specifics of Go gameplay? (Including a set of handcrafted Go-specific training features.)
- abecedarius 11y agoNxN Go is PSPACE-complete.[1] That's an even bigger deal than NP-complete. [1] According to some comment in /r/MachineLearning the other day. I haven't looked into it myself.
- jeeyoungk 11y agoThat is with some bounds applied to it - if we allow unbounded games (ko, superko, etc) then it is EXPTIME-complete.
- jxy 11y agoYes. Source here: http://senseis.xmp.net/?ComplexityOfGo http://senseis.xmp.net/?ComplexityOfGo
- euyyn 11y agoTo be fair, AlphaGo can only play 19x19 Go. It's unrelated to solving NxN Go.