It was written a specification (draft but already "functional") for automatic transformation and validation of complex (possibly multi-namespace) XML documents based on namespaces, written a software (XML Boiler) to implement these transformations. Written a short tutorial for XML Boiler.
This is HTML and LaTeX "killer".
Most of the specification was implemented in Python programming language. This project prototype "XML Boiler" is already nearly complete and is practically useful.
I don't remember enough CS theory to make heads or tails of this, but I'm just curious why post it here for review rather than taking it to a CS department somewhere or sending it to a journal for review?
You understood mostly right, but see my another comment for more detailed proof that does address this issue by ignoring zero-filled fragments of INFINITE memory.
"n" is the number of bits (what you referred to as "X").
Storing one value into a tree is O(log(X)). However, storing all possible values for X bits is 2^X operations, each of which requires log(X) sub-operations to store it.
Pre-calculating all possible input-output mappings requires looking at every possible input value. Thats 2^X.
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. So if A(y) is defined as y+1, you can code it with about X primitive logical operations. One operation could be "output[least significant bit] = xor(input[least significant bit], 1)". That operation causes a transformation to every single input value, and is thus very powerful and economical. Other operations would ripple the carry to the more significant bits; the next-to-least-significant operation transforms half of the input values, the next bit affects one quarter of them, and so on.
P =? NP asks if it's always possible to come up with a reasonably small set of transformations that go the opposite way. You can't do that with a process that looks at the discrete values. If it's possible it will require some kind of comprehension of the algorithm's structure. We can't (in polynomial time) create an inverse of "y+1" by listing what happens for each possible input value. We need to recognize that the inverse function is "result - 1" and provide the primitive operations for that.
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.
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."
I am not an employee or partner of Cartesi (however, in the future I am going to be), I even tried to be hired but wasn't. I do like Cartesi to be advertised because I like that OSS project, but not so much to spend my time in marketing them. So, no, I don't advertise them by my P=NP question.
It was written a specification (draft but already "functional") for automatic transformation and validation of complex (possibly multi-namespace) XML documents based on namespaces, written a software (XML Boiler) to implement these transformations. Written a short tutorial for XML Boiler.
This is HTML and LaTeX "killer".
Most of the specification was implemented in Python programming language. This project prototype "XML Boiler" is already nearly complete and is practically useful.