3 ms·
ML is all about finding approximate solutions. Categorizing problem as NP-complete only makes sense when talking about exact solutions.
by schwurb 8y ago
ML 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).