Interesting! Looking quickly over the argument, what it seems to be saying is this (someone please correct me if I’m misunderstanding it):
We already know that anyone with a solution to an NP problem can convince us of this in P time. (This is obvious for some NP problems e.g. propositional satisfiability, but surprising for others e.g. traveling salesman.)
Surprisingly, a variant of this extends to all PSPACE problems, if the verification procedure is allowed to be an interactive dialogue and if we are satisfied with an exponentially small probability of error. This applies even to problems like chess, via the application of nontrivial (but still polynomial time) transformations.
But it’s not jumping out at me how to extend something like this to incomputable problems. Do you have an approach in mind?
… but surprising for others e.g. traveling salesman.
A “yes” answer to the decision version of TSP (“is there a path shorter than x?”) is straightforwardly demonstrable: just specify the path. A “no” answer is not demonstrable (short of interactive provers): TSP is in NP, not coNP. And an answer to the optimization version of TSP (“find the shortest path”) is also not demonstrable (short of interactive provers): it’s FP^NP-complete, which is stronger than NP. So I don’t see any surprises there.
Alas, no. Perhaps it is impossible for someone who has a halting oracle to convince someone without a halting oracle that they have a halting oracle, even in universes whose physics allows halting oracles.
Aliens who have solved chess can convince us of that fact without showing us the solution. It would be somewhat surprising if aliens who have a halting oracle could not.
Damn, the argument is in a postscript file. That would require downloading something. I wonder if I care that much!
Recall that in the chess case the setup is this: the verifier is given a string of n random bits, asks P(n) interactive questions to the alien, and then says yes or no. If White can force a win in chess the verifier says yes in 2/3s of the cases, while if White cannot force a win the verifier says yes in only 1/3d of the cases.
It’s a deep result that you can set up a verification protocol like this for any problem in PSPACE. But it’s easy to see that it only works if the problem is in PSPACE: using P(n) space, the alien can simulate all possible question-answer interactions with the verifier, and give the answers that will make the verifier answer yes if there are any at all. So you could never use a protocol like this to prove that you possess a halting oracle, since even without an oracle you can do a finite amount of computation to figure out what answers the verifier will accept.
I would guess this principle holds in general: no matter which particular notion of “proof” or “convincing” you settle on, it will ultimately involve running a finite computation to verify a purported proof. But such a procedure can always be fooled by another (longer) finite computation.
(Edit: corrected error in the description of the protocol)
I find this suspect. If someone who was only good enough at chess to make moves at random played against a chess master, the latter would win so often that if they play for any reasonable amount of time, the former could never tell if the latter is capable of losing.
He doesn’t have to know how to do that. Any information he has regarding positions he’d never get in can be wrong and he’d still be unbeatable. This includes knowing whether or not it’s a position he can get in. The only way to reach a contradiction is if you show that he can lose from a given position, and that he can get there from a starting position.
You could try working backward by checking every position that might lead to this one and see if he moves so it does, but there might be no way to get to it, or multiple. You’d have to follow the entire tree back to prove that it doesn’t connect to the beginning. Worse, he isn’t even guaranteed to play deterministically, and just because he didn’t move to that position this time doesn’t mean he can’t.
Aliens who have solved chess can convince us of that fact without showing us the solution. It would be somewhat surprising if aliens who have a halting oracle could not.
Interesting! Looking quickly over the argument, what it seems to be saying is this (someone please correct me if I’m misunderstanding it):
We already know that anyone with a solution to an NP problem can convince us of this in P time. (This is obvious for some NP problems e.g. propositional satisfiability, but surprising for others e.g. traveling salesman.)
Surprisingly, a variant of this extends to all PSPACE problems, if the verification procedure is allowed to be an interactive dialogue and if we are satisfied with an exponentially small probability of error. This applies even to problems like chess, via the application of nontrivial (but still polynomial time) transformations.
But it’s not jumping out at me how to extend something like this to incomputable problems. Do you have an approach in mind?
A “yes” answer to the decision version of TSP (“is there a path shorter than x?”) is straightforwardly demonstrable: just specify the path. A “no” answer is not demonstrable (short of interactive provers): TSP is in NP, not coNP. And an answer to the optimization version of TSP (“find the shortest path”) is also not demonstrable (short of interactive provers): it’s FP^NP-complete, which is stronger than NP. So I don’t see any surprises there.
Alas, no. Perhaps it is impossible for someone who has a halting oracle to convince someone without a halting oracle that they have a halting oracle, even in universes whose physics allows halting oracles.
Damn, the argument is in a postscript file. That would require downloading something. I wonder if I care that much!
I don’t think the situation is comparable.
Recall that in the chess case the setup is this: the verifier is given a string of n random bits, asks P(n) interactive questions to the alien, and then says yes or no. If White can force a win in chess the verifier says yes in 2/3s of the cases, while if White cannot force a win the verifier says yes in only 1/3d of the cases.
It’s a deep result that you can set up a verification protocol like this for any problem in PSPACE. But it’s easy to see that it only works if the problem is in PSPACE: using P(n) space, the alien can simulate all possible question-answer interactions with the verifier, and give the answers that will make the verifier answer yes if there are any at all. So you could never use a protocol like this to prove that you possess a halting oracle, since even without an oracle you can do a finite amount of computation to figure out what answers the verifier will accept.
I would guess this principle holds in general: no matter which particular notion of “proof” or “convincing” you settle on, it will ultimately involve running a finite computation to verify a purported proof. But such a procedure can always be fooled by another (longer) finite computation.
(Edit: corrected error in the description of the protocol)
I find this suspect. If someone who was only good enough at chess to make moves at random played against a chess master, the latter would win so often that if they play for any reasonable amount of time, the former could never tell if the latter is capable of losing.
Who says you have to test the chessmaster only on board positions you can reach by playing from the canonical opening position?
You should be able to ask the supposed chess-solver about whether and how to win from arbitrarily-chosen board positions.
He doesn’t have to know how to do that. Any information he has regarding positions he’d never get in can be wrong and he’d still be unbeatable. This includes knowing whether or not it’s a position he can get in. The only way to reach a contradiction is if you show that he can lose from a given position, and that he can get there from a starting position.
You could try working backward by checking every position that might lead to this one and see if he moves so it does, but there might be no way to get to it, or multiple. You’d have to follow the entire tree back to prove that it doesn’t connect to the beginning. Worse, he isn’t even guaranteed to play deterministically, and just because he didn’t move to that position this time doesn’t mean he can’t.