5
$\begingroup$

I'm interested in proving that finding optimal play in a particular two-player game is harder than the arithmetic hierarchy. I suspect this to be true, because even carrying out a deterministic end-game to it's conclusion is Turing complete. I was hoping to complete my proof via encoding in it the following game:

The Polynomial Equation Game: Let $n$ be any positive integer and let $P$ be a multivariate polynomial with $n$ variables and integer coefficients. We define a two-player game by letting each player pick an integer of their choice, alternating picks until $n$ integers (not necessarily distinct) have been picked. The first player wins if $P(x_1,\ldots , x_n)=0$.

It follows from Matiyasevich's theorem (plus a little algebra work) that optimal play for every $P$ and every $n$ harder than the arithmetic hierarchy. Unfortunately, this has turned out to be quite difficult to encode due to the rules of my game.

As I have been able to model a universal Turing machine in a deterministic version of my game, I am considering if that can be extended to the proof I am after. One idea I've had is the following:

The Monotonic Turing Machine Game: Let $\Phi$ be a universal Turing machine and let $n$ be an integer. We define a two-player game by letting each player pick a non-blank symbol (out of those that $\Phi$ reads) of their choice and set any blank cell of the input tape to that symbol. Players take turns picking symbols and writing to cells until $n$ symbols (not necessarily distinct) have been picked. The first player wins if $\Phi$ halts on the input constructed in this fashion.

Suppose that we have a globally-fixed $\Phi$ and encoding for the tape. Is it the case that optimal play for every $n$ is AH-hard? This intuitively feels like it should be the case, but the monotonicty of the input is tripping me up. Additionally, it is not the case that this game is $\Delta^0_n$-complete for each $n$, in stark contrast to the Polynomial Equation Game. It seems reasonable that, for infinitely many $n$, this game for a given $n$ is $\Delta^0_n$-complete (or $\Delta^0_{f(n)}$-complete for some unbounded $f:\mathbb N\to\mathbb N$) but I don’t see how to prove it because previous proofs along these lines I’ve done have all been inductive.

If the answer depends on the Turing machine in question, let's say it is the $(2, 18)$ universal Turing machine.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Like PH, AH has no complete problems unless it collapses. Unlike PH, we know unconditionally that AH doesn't collapse. Did you instead mean something like "arithmetic-complete" (by which I mean the class which is to AH as PSPACE is to PH)? Not sure this is a standard term. $\endgroup$
    – Joshua Grochow
    Commented Sep 6, 2018 at 1:46
  • 1
    $\begingroup$ @JoshuaGrochow Yes, maybe instead of AH-complete, say Turing equivalent to $0^{(\omega)}$, where $0^{(\omega)}$ is the set whose $n$th column is the canonical $\Sigma^0_n$-complete set $0^{(n)}$. $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Sep 6, 2018 at 6:24
  • $\begingroup$ @JoshuaGrochow Interesting, what I had in my head was “harder than $0^{(n)}$ for every $n$” which seems like Bjorn’s $0^{(\omega)}$ is an example of. I’m curious why this isn’t AH-complete though, as anything in the arithmetic hierarchy is solvable with an oracle to $0^{(n)}$ for some $n$ and by definition $0^{(\omega)}$ is harder than that. Likewise I would have called Truth AH-complete. I’m not familiar enough with PH to comment on PH comparisons. $\endgroup$
    – Stella Biderman
    Commented Sep 6, 2018 at 12:26
  • 2
    $\begingroup$ @BjørnKjos-Hanssen oh, I see. An X-complete set must be an element of X. I meant to say AH-hard. I think that addresses all of the comments? $\endgroup$
    – Stella Biderman
    Commented Sep 6, 2018 at 12:31
  • 1
    $\begingroup$ Yes, AH-hard would also be fine :). But I think Bjorn's solution (equivalent to $0^{(\omega)}$) is a good one, as it exactly characterizes The Polynomial Equation Game. (And is a good formalization of what I was trying to get at as well.) $\endgroup$
    – Joshua Grochow
    Commented Sep 6, 2018 at 22:12

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.