Translating a new problem to any problem that has already been proven to belong to that complexity class suffices.
It's the other way around. Translating a problem with a known complexity class to the new problem(in time P) indicates the complexity class.
Re:
by andrewflnr on Tuesday April 30, 2024 @12:27PM
(#40212823)
They 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.
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 ?