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

## Advertising

`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"" <[EMAIL PROTECTED]>`

To: <everything-list@eskimo.com>; <[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 anHPObox 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 stilltest an HPO box by generating random instances of hard problems withknownsolutions. (That is, you generate a random solution first, then generatearandom problem with that solution in mind.) For example here's a pageaboutgenerating random instances of the Traveling Salesman Problem with known optimal solutions. http://www.ing.unlp.edu.ar/cetad/mos/FRACTAL_TSP_home.htmlThat'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