4 ms·
Well, according to this paper, ML can't do too well, unless you can use ML to solve NP-complete problems.
by ComplexSystems 8y ago
Well, according to this paper, ML can't do too well, unless you can use ML to solve NP-complete problems.
- hopler 8y agoWhat does "too well” mean? The paper proves that Tetris is NP hard, but that is only because Tetris is infinitely long game. It's still easy for a computer to play as well as a human and faster
- bjourne 8y agoThat is the "even to approximate" part. It means that Tetris is NP-hard AND no polynomial time algorithm can be shown to be within a constant factor of the optimal solution. Eg no matter how good your Tetris bot is, there may be one that is a thousand times better waiting to be discovered.
- schwurb 8y agoML is all about finding approximate solutions. Categorizing problem as NP-complete only makes sense when talking about exact solutions.
- mlevental 8y agothat's not true at all https://en.m.wikipedia.org/wiki/Approximation_algorithm#Hardness_of_Approximation https://en.m.wikipedia.org/wiki/Approximation_algorithm#Hard...
- schwurb 8y agoPlease point out where I am (completely!) wrong. I have formally dealt with approximation algorithms before and I skimmed the wikipedia article, yet I did not find anything that contradicts me. Note the in the section on hardness, P and NP (obviously) appear as bounds of solutions. Where is the contradiction? Further, all this (approximation algos and P/NP algos) are discrete, complete algorithms. ML is a completely different story, as one is never certain whether some optimum is global or local. Hence, ML is a heuristic, while Djikstras shortest path algorithm is a series of steps with a success guarantee (with provable worst runtime behavior).