4 ms·
Maybe I'm wrong but wasn't a property of NP-hard problems that you can verify them in P time but find a solution only in >P time? (As far as we know)
by xg15 9y ago
Maybe I'm wrong but wasn't a property of NP-hard problems that you can verify them in P time but find a solution only in >P time? (As far as we know)
- eru 9y agoNP can only verify positive solutions in P time. Useful cryptographic problems are usually in the intersection of NP and co-NP. Current best guess is that NP and co-NP are different. Thus NP complete problems can't be in co-NP, and thus are probably not cryptographically useful. There's a way to make this argument a bit less vague, but it basically explains why cryptographers have stopped looking at NP complete problems. There was a cryptosystem based on solving knapsack problems. But they had to patch problems until people stopped paying attention.
- BLanen 9y agoWell, 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.