What if all things computable are computable in polynomial time?

[Bill Stewart]

At 03:50 PM 08/06/2003 -0700, Major Variola (ret) wrote:
>Yes, but the cryptanalysis of symmetric ciphers involves
>exponentially-expanding "back trees".
>That is the whole point of "avalanche".  If, somehow, "for any NP
>algorithm there were an equivalent P algorithm",
>then the block-cipher backtracking would be solvable in poly time.
>You could find the plaintext ASCII needle in the haystack
>of possibilities in poly time, no?

No.  NP is the set of problems which can be solved in
poly time on a non-deterministic Turing machine,
i.e. which can be solved in poly time if the
magic oracle correctly tells them a poly number of answer bits.
Not all exponential problems fit this model.