Mathematical thought experiment: what would the world look like if Hilbert’s Programme had succeeded?
Background: Hilbert’s programme was about arithmetic of whole numbers. His challenge to mathematicians of the early 20C was to find a complete list of axioms, and a practical method to determine whether any statement about arithmetic is true or false.
It was wrecked first by Gödel and then by Turing and others.
But can we imagine what the future that Hilbert had envisioned might look like?
There would be ~no cryptography: no asymmetric signing/encryption schemes and no key extension schemes, so the only way to symmetrically encrypt something would be to use a key the size of the message.
Solving real-world problems by reducing them to a SAT instance (or something universal of a similar nature) would be even more popular. That would probably eat all the hard problems in operations research for example.
Approximate algorithms would be a lot less important and probably wouldn't develop as a field for some time: there'd be very little reason to use them (perhaps some polynomial speedup).
Finding "fastest algorithm for problem X" could be also done automatically once we describe X well enough, so a nontrivial amount of effort would move to making such descriptions easy to write in an obviously-correct fashion.
@robryk @richardelwes I'm confused by this. Public-key cryptography doesn't depend on Gödel incompleteness, just on the computational complexity of things like the factoring problem. In an alternate mathematical universe where all problems in arithmetic were decidable, there'd be no _a priori_ reason to assume that complexity would be affected.
@robryk @richardelwes We might have to spend less effort on finding the "true" complexity of a problem, but there could easily still be problems that take O(2^n) or worse time.
> and a practical method to determine whether any statement about arithmetic is true or false.
I understood this as meaning "polynomial-time algorithm that determines whether a given statement expressed in arithmetic is true/provable (which would be the same in that world)". If so, NP=P, because you can ask your truth-determining system whether a witness exists.
Note that even if we relax the requirement to "proof-finding algorithm that finds ~shortest proof and is polynomial _in output size_", we still get P=NP by those means.
> but there could easily still be problems that take O(2^n) or worse time.
On the face of it, obviously EXPSPACE is still strictly larger than PSPACE (and EXPTIME is still strictly larger than P), so this should be true. OTOH, can't we describe some EXPSPACE-complete or EXPTIME-complete problem in arithmetic using a description sized polynomially in its input? I'd expect yes, and if so this provides yet another proof why determining truthfulness couldn't be polynomial in _input_ size. (Though this probably wouldn't be such a simple contradiction in the setup where we have an algorithm polynomial in proof length.)
@robryk @richardelwes I guess it depends what you interpret "practical" to mean. I was assuming the rather weak definition of "not actually undecidable" which I concede is not the only possible meaning :)
(I'm not sure that Hilbert would specifically have had "polynomial time" in mind, though.)
In that case you can make that world arbitrarily close to our own by making those truth-detectors arbitrarily computationally expensive.
