Dear Hal and Wei Dai,
One question: Does it not make sense that if there did exist an instance
of a P=NP computation within our physical universe that Nature would not
have found a way to implement it widely? The fact that the folding of
proteins, a known NP complete problem, takes a relatively long time to
actually occur tells me that such a computation, at best, only occurs is
very special situations in our universe, situations that can not be
converted (via a polynomial transformation) to solve problems in other
There is an old saying: What ever Man can do, Nature is already doing,
Nature is performing computations all the time and what we experience is
the best computation possible.
It is only our failure of imagination that leads us to endlessly follow
rabbit trails. ;-)
----- Original Message -----
From: ""Hal Finney"" <[EMAIL PROTECTED]>
To: <firstname.lastname@example.org>; <[EMAIL PROTECTED]>; <[EMAIL PROTECTED]>
Sent: Friday, July 22, 2005 12:43 PM
Subject: Re: is induction unformalizable?
Wei Dai writes:
1. P=?NP is a purely mathematical problem, whereas the existence of an
box is an emperical matter. If we had access to a purported HPO box while
P=?NP is still unsolved, we can use the box to exhaustively search for
proofs of either P=NP or P<NP.
I've seen many speculations that P=?NP may be undecideable under our
current axioms. I guess this is because people are tired of looking
for proofs and PhD students don't want to get assigned this problem.
I'm not sure whether both of the following possibilities would be
consistent with the issue being undecideable:
A: There actually exists a polynomial-time algorithm to solve all
NP problems, but we can't prove that it always works, even though it
B: There is no polynomial time algorithm that solves all NP problems,
but we can't prove that no such algorithm exists.
I wonder if we could ask the HPO (halting problem oracle) box any harder
questions, that might help resolve the issue if it turned out that P=NP
is undecideable. Could we use it to directly ask whether the algorithm
in case A above exists, and perhaps even to find it?
2. I think it's very unlikely that P=NP, but in case it is, we can still
test an HPO box by generating random instances of hard problems with
solutions. (That is, you generate a random solution first, then generate
random problem with that solution in mind.) For example here's a page
generating random instances of the Traveling Salesman Problem with known
That's a good idea, but is it known that this subset of problems is
still NP-hard? I would worry that problems like these, where a fractal
or space-filling curve type of path is the right solution, might turn
out to be easier to solve than the general case.