Take the tour ×

Let $n$ be a member of $\omega$, which the omnipotent provers $Y$ and $N$ know. A Turing machine will be run starting with the $n$ already inputted, and the machine can have a natural number inputted from the prover of its choice, with no limit on the number of times it can do so.

Let $S$ be a subset of $\omega$.

Definition: S is decidable from competing provers if and only if

there exists a Turing machine such that, for all members $n$ of $\omega$, when run as above,
(1) if $n\in S$ then $Y$ has a strategy that will force the Turing machine to accept
(0) else $N$ has a strategy that will force the Turing machine to reject

What subsets $S$ of $\omega$ are decidable from competing provers?
What if the Turing machine is required to always halt?
In each case, is the resulting class low for itself?

share|improve this question
add comment

4 Answers

up vote 7 down vote accepted

The result I expected in my previous answer turns out to be correct and somewhat easier than the old paper that led me to expect it. Here's a proof that "decidable from competing provers" is equivalent to "hyperarithmetical."

Suppose first that $S$ is decidable from competing provers, and fix a Turing machine $M$ as in the statement of the problem. Then a natural number $n$ is in $S$ if and only if there is a strategy $s$ for player $Y$ such that, for no finite sequence $p$ of moves of $N$ does the machine $M$ reject after $N$ has played $p$ (without asking for any further inputs from $N$). Because we need only consider finite plays by $N$, and because the operation of a Turing machine can be described arithmetically, this characterization of $n\in S$ involves only one quantifier that goes beyond arithmetic, namely "there exists a strategy $s$"; that's one existential quantifier over (what amounts to) reals, so $S$ is a $\Sigma^1_1$ set. A symmetrical argument shows that the complement of $S$ is also $\Sigma^1_1$, and therefore $S$ is hyperarithmetical.

For the converse, let $S$ be any hyperarithmetical set, and fix $\Sigma^1_1$ definitions, in normal form, for both $S$ and its complement. So we have recursive predicates $P$ and $Q$ such that, for all $n$,

  • $n\in S$ iff there is a function $f:\mathbb N\to\mathbb N$ such that, for all $k\in\mathbb N$ the restriction $\bar f(k):=f\upharpoonright\{0,\dots,k-1\}$ satisfies $P(n,\bar f(k))$, and

  • $n\notin S$ iff there is $g:\mathbb N\to\mathbb N$ such that, for all $k\in\mathbb N$ we have $Q(n,\bar g(k))$.

Let $M$ be the Turing machine that, given input $n$, alternately asks $Y$ and $N$ for natural numbers, interpreting $Y$'s (resp. $N$'s) inputs as successive values of $f$ (resp. $g$). After each value is received, the machine checks whether $P$ (resp. $Q$) holds of $n$ and the sequence of values of $f$ (resp. $g$) received so far. They can't both continue to hold forever, since that would put $n$ into both $S$ and its complement. As soon as a failure occurs, $M$ says that $n$ is not (resp. is) in $S$ if $P$ (resp. $Q$) failed first. Now if in fact $n\in S$, then $Y$ can give $M$ the values of an appropriate witness $f$ so that $P$ will never fail. Therefore $Q$ will eventually fail (no matter what $N$ does), and $M$ will correctly decide that $n\in S$. Symmetrically, if $n\notin S$, then $N$ can make $M$ say so, by playing a witness $g$. Therefore, $M$ decides $S$ from competing provers.

share|improve this answer
The second part of this proof shows that, for a suitable Turing machine $M$, the game between $Y$ and $N$ is not as interactive as one might think. The winning player doesn't need to pay any attention to what the other player is doing. If $n\in S$ then $Y$ can simply play a fixed witness $f$, ignoring $N$'s moves, and symmetrically if $n\notin S$ then $N$ can play a fixed witness $g$, ignoring $Y$'s moves. –  Andreas Blass Jul 29 '11 at 3:31
Your first implication seems to only work for the always-halts version. Is the normal form of a $\Sigma_1^1$ definition supposed to be prenex disjunctive normal form with the set quantifier first? –  Ricky Demer Jul 29 '11 at 3:35
Also, you don't need a complexity analysis to show that a TM can be chosen so that strategies can be chosen to be non-interactive. Just have the player give a sequence coding what their inputs would be to the interactive version after any finite sequence of inputs from the other player. This translates the main question into one about computably open subsets of $\omega \times (\omega^{\omega})^2$, although I don't see that that helps. –  Ricky Demer Jul 29 '11 at 3:58
Concerning Ricky Demer's second comment: You're right; the rules of such games can always be adjusted so that the winner can ignore the loser's moves. So my first comment wasn't worth making. –  Andreas Blass Jul 29 '11 at 5:18
It's also theorem V.1.4 in Simpson's "Subsystems of Second-Order Arithmetic", and the proof there is very clear. –  Carl Mummert Jul 29 '11 at 11:19
show 4 more comments

This seems to be very closely related to an old paper of mine, "Complexity of Winning Strategies" (Discrete Math. 3 (1972) 295-300). That paper concerned games that "can really be played" in the sense that the moves are natural numbers (or similar finitary objects), the game is sure to end after finitely many moves, and there is an algorithm to tell, given any position, (1) whether the game has ended, (2) if so, who won, and (3) if not, who is to move next. Because of the finite termination requirement, one of the players has a winning strategy. The main result in the paper is that one of the players has a hyperarithmetical winning strategy and this is optimal, in the sense that, for any hyperarithmetical set $A$, there is a game of this sort such that $A$ is computable from every winning strategy.

The question at hand is not exactly the same, since it's about deciding who wins rather than finding the winning strategy. I strongly suspect, though, that the same method will give the corresponding result --- in fact with a better form of optimality, since "computable from a set decidable from competing provers" simplifies to "decidable from competing provers". I therefore expect that "decidable from competing provers" is equivalent to "hyperarithmetical."

share|improve this answer
add comment

A partial answer is that the class includes all arithmetical sets, as follows. Suppose $S$ is defined by a formula $\psi(n) \equiv (\exists a)(\forall b)(\exists c)(\forall d) \cdots \phi(n, a, b, c, d, ...)$ where $\phi$ is quantifier free. By adding dummy quantifiers we can require that the quantifiers all occur in blocks of two like that, exists followed by forall. A function to decide $S$ from competing provers is as follows. First it asks $Y$ for a value of $a$. Then it asks $N$ for a value of $b$ given $a$. Then it asks $Y$ for a value of $c$ given $a$ and $b$, and so on. Once it has values for all the variables in $\phi$, it checks whether $\phi$ holds with those values plugged in. If so, it accepts $n$, and if not it rejects $n$.

If $n \in S$ then $Y$ has a winning strategy, because $\psi(n)$ is true. All $Y$ has to do is pick appropriate values for each existential quantifier, which have to exist if $\psi(n)$ holds. Otherwise, $\lnot \psi(n)$ is true, so $N$ has a winning strategy using the same technique of picking witnesses for the existential quantifiers in $\lnot \psi$.

Not every set in $S$ is arithmetical, though. As usual let $0^{a}$ be the $a$-th iterated Turing jump of the empty set. Consider $$S = 0^{(\omega)} = \{ 2^a3^b : b \in 0^{a}\}.$$ This is not an arithmetical set, but it can be accepted from competing provers as follows. First the machine looks at the input $n$ and decodes it into $2^a3^b$. If the number is not of that form the machine can just reject out of hand. If it is of that form, the machine pretends that it was given input $b$ and checks whether that number is in $0^{a}$ using $Y$ and $N$. Because an arithmetical formula for $0^{a}$ is uniformly recoverable from $a$, this can be done effectively, and $Y$ and $N$ will have the appropriate strategies because $0^{a}$ is arithmetical.

Note all the machines in this answer so far will halt on all strategies, and in fact we can give a bound on how many queries the machine will make as a function of $n$.

share|improve this answer
It seems to me that you can do this uniformly also since the number of alternations can depend on n, i.e. the class contains the truth predicate for arithmetic formulas, and the reverse also holds so I think the answer is the class is $(\Delta^1_0)′$. Also TM not halting does not change the class. –  Kaveh Jul 29 '11 at 1:22
@Kaveh: the idea of $0^{\omega}$ occurred to me as well, I was writing it up at the same time you commented. I don't yet see how to give a full characterization, though. Because the oracles can give any natural number as output, quantifying over wining strategies seems difficult. –  Carl Mummert Jul 29 '11 at 1:24
I will fix the notation $0^{(a)}$ the next time I edit the question. The preview broke when I was writing it. –  Carl Mummert Jul 29 '11 at 1:26
add comment

In computational complexity theory, the polynomial-time version of your class is known as $S_2P$. For a brief description, see here: http://qwiki.stanford.edu/index.php/Complexity_Zoo_1.0#s2p

It occurs in a few interesting complexity theorems.

share|improve this answer
As far as I can see, $S_2^P$ would correspond to the case where the game is restricted to one round. –  Emil Jeřábek Jul 29 '11 at 15:45
In fact, the argument in Carl's answer above shows that the polynomial-time version of Ricky's class includes all of polynomial hierarchy. On the other hand, it is included in $\mathrm{NEXP}\cap\mathrm{coNEXP}$ since $\mathrm{MIP}=\mathrm{NEXP}$. –  Emil Jeřábek Jul 29 '11 at 15:57
add comment

Your Answer


