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,
Stephen
----- Original Message -----
From: ""Hal Finney"" <hal.domain.name.hidden>
To: <everything-list.domain.name.hidden>; <hal.domain.name.hidden.org>; <weidai.domain.name.hidden.com>
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.
>>
>> http://www.ing.unlp.edu.ar/cetad/mos/FRACTAL_TSP_home.html
>
> 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
Received on Fri Jul 22 2005 - 14:41:34 PDT