3 ms·
Well, Think of the traveling salesman problem for example. The only way to verify someone's answer is to do all of it yourself too.
by BLanen 9y ago
Well,
Think of the traveling salesman problem for example.
The only way to verify someone's answer is to do all of it yourself too.
- ctchocula 9y agoYou can do it by checking that the solution provided is a valid traversal of the graph, and does not touch two vertices twice. If there are N vertices, you can check in O(N) time.
- BLanen 9y agoIt's about validating the proposed solution on being the fastest path, not if the proposed solution is a valid path.