3 ms·
One subtlety this video skips over, is that P and NP are defined as classes of decision problems, rather than arbitrary computational problems. So when they ta
by tromp 3y ago
One subtlety this video skips over, is that P and NP are defined as classes of decision problems, rather than arbitrary computational problems.
So when they talk about the problem of finding the number of moves it takes to unscramble a Rubik's cube, you need to translate that into a decision problem in order to place it into one of these classes. If you can then solve the decision problem efficiently, you should be able to use that to solve the computational problem efficiently.
That could be: given a Rubik's cube and an integer k, is it possible to unscramble it in at most k moves.
When the problem is to find the discrete log of a curve point on an Elliptic Curve, the decision version could be:
given a point P on a curve of order < 2^n with generator G, and a bitstring x of length at most n, is there a n-bit number k with prefix x such that P = xy * G ?
- nabla9 3y agoTranslating a new problem to any problem that has already been proven to belong to that complexity class suffices.
- Daimanta 3y agoIt's the other way around. Translating a problem with a known complexity class to the new problem(in time P) indicates the complexity class.
- andrewflnr 3y agoThey explicitly swept all the differences between different NP-complete problems under the rug as "some polynomial-time complexity", so I don't think he's worried about the translation between decision problems and others. He's trying to explain the broad significance of P vs NP for non-computer-scientists, so I'd agree that level of "subtlety" isn't necessary. Someone who cares and puts in the effort won't have a problem taking that in stride if they want to learn the full version later.