2 ms·
Ahhh. I think there's a misunderstanding. Proving P=NP is saying "given, for algorithm A, that it's easy to verify any proposed result y and input x, it follow
by mgsouth 5y ago
Ahhh. I think there's a misunderstanding.
Proving P=NP is saying "given, for algorithm A, that it's easy to verify any proposed result y and input x, it follows that it's also easy to calculate a result for any input I'm given." It does not mean "given any proposed input x and output y, if I verify x I can quickly re-calculate y."
For example, suppose y=A(x) -> y is the smallest prime factor of x. A is in NP, since if we are given an x and y we can quickly verify it. Proving P = NP would mean that we can also quickly, given just an x, figure out a y.
Your proposal seems to be "given an x and y, keep track of the steps as we verify y -> x and then use them as hints to re-calculate y from x."