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 situations.

There is an old saying: What ever Man can do, Nature is already doing, better.

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. ;-)

Kindest regards,


----- Original Message ----- From: ""Hal Finney"" <[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 HPO
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
always does.

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 known solutions. (That is, you generate a random solution first, then generate a random problem with that solution in mind.) For example here's a page about
generating random instances of the Traveling Salesman Problem with known
optimal solutions.

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.

Hal Finney

Reply via email to