and if we can find a polynomial-time algorithm approximating the exact
solution within a few percent, we can save substantially on both fuel and
time. “Good enough” is sometimes more than good enough.Two Predictions I Feel Are Likely
A common theme that emerges from many of the problems that we have
examined is that if the system we are describing is sufficiently complex,
there will be truths that we will be unable to ascertain. Of course, the
paramount example of this is Gödel’s result on undecidable propositions,
but I would expect that mathematicians and logicians of the future would
be able to do one of two things: either describe what makes an axiomatic
system sufficiently complex to admit undecidable propositions, or show
that such a description is impossible. There may already be partial results
in this area, but if the latter result had been proven, I think it would be a
sufficiently breathtaking result that it would be widely known in the math-
ematical community. I think the same will hold for Hilbert’s quest to axi-
omatize physics: either it will be shown that this cannot be done
successfully, or if successful, it will result in physical analogues of unde-
cidable propositions. The existence of analogues of the uncertainty princi-
ple will arise not from a quantum hypothesis (although that hypothesis
specifically resulted in the uncertainty principle), but from the axiomati-
zation itself. That axiomatization will show that there must be results
along the lines of the uncertainty principle, but it will not tell us what
those results are.
I admit there is a certain vagueness about the predictions made in the
previous paragraph, so I will offer a more concrete one. It will be shown
for every one of the myriad of NP-hard problems that any polynomial-time
algorithm devised for solving it admits anomalies of the form we encoun-
tered when discussing how priority-list scheduling can lead to situations
in which making everything better makes things worse. This was also
seen when we applied the nearest neighbor algorithm to the traveling
salesman problem; it is easy to construct an array of towns and distances
between them such that, if all the distances were shortened, the nearest
neighbor algorithm resulted in a path with a longer total distance than the
total distance given by that algorithm for the original configuration.
If I were a young, but tenured, specialist in this area (the specification of
tenure is necessary because this might be a problem requiring an im-
mense amount of time, and you don’t want to risk your chance of tenure
on a problem for which you might not achieve quick results), or a mature
specialist who was looking for an eye-opening result, I’d give this one a
Through a Glass Darkly 241