4 ms·
Why did we escape the land of NP?
by heavenlyblue 4y ago
Why did we escape the land of NP?
- FartyMcFarter 4y agoNP problems are ones whose positive solutions are verifiable in polynomial time. For example, the problem "is there a route in this graph that visits all nodes and has length <= L" can be quickly verified with a classical computer, as long as you're given a "yes" answer accompanied by such a route. Finding the answer from scratch might be much slower, but checking it is quick.