2 ms·
The number of bits is s(X) not X. So, the rest in your response is in error. Why do you think my proofs needs to pre-calculate all possible input-output mappin
by porton 5y ago
The number of bits is s(X) not X. So, the rest in your response is in error.
Why do you think my proofs needs to pre-calculate all possible input-output mappings? I use only verification that a particular input corresponds to a particular output (and I prove that this verification is polynomial-time.)
"That isn't what P =? NP is looking for. The forward function, A, isn't a big look-up table. Instead, it's a much smaller set of transformational steps." - no idea what you mean.
No comment on obvious (and true) things you said after this.
- mgsouth 5y agoAhhh. 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."