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 ?