What if all things computable are computable in polynomial time?

[Bill Stewart]

> >What if all things computable are computable in polynomial time?

Lots of problems are only computable in exponential time,
or at least superpolynomial time.
The closest we'd get to your suggestion is that
P might equal NP, or (for crypto) factoring might be in P.

Sufficiently large polynomials are easier in theory than in practice -
Karmarkar's polynomial solution to Linear Programming was
something like N**12 or L*N**6 where L was a very large number.

>We would have to go back to paper and OTP, but we would also get to
>enjoy the excellent graphics, AI, number theory, etc, that we would win.

We wouldn't have to go back to OTP, just symmetric-key keyservers
which people used before public-key became well-known.

While the public-key algorithms are based on math problems like
factoring or discrete log, most of the symmetric-key algorithms
are based on intractable ugliness, and on doing enough analysis
to find out which kinds of ugliness and bit-twiddling are really
intractable and which can be cracked.

If the polynomial computability comes from quantum computers,
some of the symmetric stuff seems to reduce from 2**N time to 2**(N/2) time,
so we might need to upgrade from 3DES to 5DES or 7DES, but it's not big deal.