Couple of comments to the post below.
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.
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
----- Original Message -----
From: ""Hal Finney"" <hal.domain.name.hidden>
To: <everything-list.domain.name.hidden>
Sent: Saturday, July 16, 2005 12:29 AM
Subject: Re: is induction unformalizable?
> One question I am uncertain about is this: how well could we test a
> supposed halting-problem oracle (HPO) box?
>
> In particular I wonder, suppose it turns out that P=NP and that further
> there is an efficient algorithm to solve any NP problem. For those
> unfamiliar with this terminology P means polynomial time, and we say
> that problems in P can be solved efficiently. NP means nondeterministic
> polynomial time, and essentially this means that for problems in NP, we
> can efficiently test a purported solution for correctness. Whether P
> is equal to NP or merely a subset of it is one of the major unsolved
> problems of computer science.
>
> But what if the aliens have solved it, and (somewhat to our surprise)
> the answer is that every NP problem can be efficiently solved. And they
> have embedded this NP solving algorithm (along with some other ones)
> in the HPO box.
>
> My concern is that to test the HPO box we could for example give it
> a problem we have solved and see if it gets the answer. But success
> might just imply that the HPO had substantially (but not astronomically)
> greater computing power than the human race can bring to bear. Or we
> could give it a problem we can't solve and then check the answer the
> HPO gives, but if the answer is testable that would mean it is in NP,
> and so even success in this area could be explained if P=NP as above.
>
> It is much less philosophically challenging to imagine that P=NP than
> to imagine that a true HPO could exist. Things would be different if
> we ever get a proof that P < NP but we aren't in that situation now.
>
> Are there other tests we could give, harder ones, that could give us
> evidence that it was a true HPO, that could not be fooled by an NP solver?
>
> My knowledge of these areas is pretty spotty. The only non NP problem I
> know of offhand is the travelling salesman problem, finding the shortest
> path visiting everyone of a set of cities with specified distances
> between each pair. Proposed solutions cannot be tested efficiently,
> as far as I know. If the box solved travelling salesmen problems for
> us, it might be a boon to salesmen but we would not necessarily know if
> we were getting truly optimal paths.
>
> So in Wei's story, when the scientists go to test the HPO box, how strong
> is the evidence that they can reasonably expect to get for it being a
> real HPO? And I suppose a practical point arises as well; even if it
> is not a true HPO, if it is nevertheless able to solve every problem we
> give it, it's probably worth the money!
>
> Hal Finney
>
Received on Fri Jul 22 2005 - 05:39:57 PDT