I denote s(X) the size of data X (in bits). I denote execution time of an algorithm A as t(A,X).

Using a Merkle tree technology similar to one of the Cartesi crypto (but with a true random number generator, and possibly the size of hashes themselves growing logarithmically), the size of the data and time to be used to verify the result of a decision algorithm X non-deterministically is log t(A,X).

Take some algorithm A in NP. It’s execution time is bounded by a2s(X) (X is input data size).

Therefore it can be non-deterministically verified in log(a2s(X))∼s(X) time.

A decision problem f can be made in the same in both directions (up to a polynomial) complexity bijective function x↦(x,f(x),h(f,x)) where h(f,x) is our hash of the Merkle tree (e.g. the Merkle tree of the “tracing” of the execution of an algorithm verifying the first Merkle tree).

So, an algorithm that computes a bijective function, which is exponential-time in both directions, is (for every bit of output) in NP (in both directions), because it is non-deterministic polynomial time (in both directions).

Therefore, it is polynomial-time (in both directions).


Note that it does not give an efficient NP-complete algorithm.

Addendum: We can restrict to SAT to make the algorithm halting for both 0 and 1 answer (for every bit).

Leave a Reply

Your email address will not be published. Required fields are marked *