One question I am uncertain about is this: how well could we test a supposed halting-problem oracle (HPO) box?

## Advertising

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