3 ms·
Irrelevant nitpick: NP-complete problems aren't "waiting" to be solved by anybody. In a strict theoretical sense, if a problem is NP-complete, there does not ex
by vecter 10y ago
Irrelevant nitpick: NP-complete problems aren't "waiting" to be solved by anybody. In a strict theoretical sense, if a problem is NP-complete, there does not exist a polynomial time solution (assuming P!=NP).
That having been said, researchers are still interested in algorithms for many NP-complete problems that are of practical utility. They often involve approximations, randomization, parameterizations, and heuristics to solve some/many problem instances in a computationally tractable amount of time.
- nickpsecurity 10y agoIrrelevant nitpick 2: we seem to have two, different definitions of solution. You must read a lot of math and NP-complete articles where you think solved means something only in the most technical sense. Whereas, a solution for the rest of us is an answer to a NP-complete problem that works effectively. The methods behind good ones take considerable brains to develop. Unlike accounting 101. ;)
- simula67 10y agoYes, what is waiting to be solved is whether or not P = NP.