3 ms·
NP 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
by FartyMcFarter 4y ago
NP 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.