10
$\begingroup$

This is a generalization of my previous question.

Let $M$ be a polynomial-time deterministic machine that can ask questions to some oracle $A$. Initially $A$ is empty but this is can be changed after a game that will be described below. Let $x$ be some string.

Consider the following Alice and Bob game. Initially, Alice and Bob have $m_A$ and $m_B$ dollars respectively. Alice wants $M^A(x)=1$ and Bob wants $M^A(x)=0$.

At every step of the game a player can add some string $y$ to $A$; this costs $f(y)$ dollar, where $f: \{0,1\}^* \to \mathbb{N}$ is a polynomial-time computable function. Also a player can miss his or her step.

The play ends if both players spends all money or if some player missed step when he or she in a losing position (that defines by the current value of $M^A(x)$).

Question: is the problem of defining the winner of this game for given $M, f, x, m_A, m_B$ is an

EXPSPACE-complete task?

Note that $M$ can ask (for belonging to $A$) only strings of polynomial length so there is no sense for Alice or Bob to add more longer strings to $A$. Hence, this problem is in EXPSPACE.

In my previous question adding of every string to $A$ costs one dollar (i.e. $f \equiv 1$). Then (as it was shown by Lance Fortnow) this game belongs to EXPH and even to PSPACE if $m_A = m_B$.

$\endgroup$
  • $\begingroup$ Can you explain why you made this change to the problem? Alice can check to see if she can afford to pay for all the strings in $S$ (as defined in Lance’s answer to your other problem) in polynomial time. How does this not immediately resolve the problem? $\endgroup$ – Stella Biderman Oct 27 '18 at 3:11
  • $\begingroup$ @StellaBiderman Alice indeed can check this in polynomial time. However, if she has not enough money then now this is does not mean that she can make only polynomial steps (as it was in the previous game). $\endgroup$ – Alexey Milovanov Oct 27 '18 at 15:28
  • $\begingroup$ If she cannot afford $S$, can she ever beat an opponent who always skips their turn? Maybe there’s something about the game set-up I am not understanding. $\endgroup$ – Stella Biderman Oct 27 '18 at 15:54
  • 1
    $\begingroup$ @Stella Yes, because their might be other accepting paths. E.g., suppose if $x_1\in A$, then $M$ stops and accepts. In this case, $S=\{x_1\}$. But if $x_1\notin A$, then $M$ might query $x_2$ and accept if $x_2\in A$. In this case it is enough if Alice has enough spondulix for $x_2$. $\endgroup$ – domotorp Oct 27 '18 at 20:56
4
+25
$\begingroup$

This should be EXPSPACE-complete. I'll sketch how to achieve an exponential number of alternations, without reducing any EXPSPACE-complete problem to this one, but from here it should be simple to finish.

Denote the words in the oracle after $t$ rounds by $A_t$, so initially $A_0=\emptyset$. Denote the words queried by $M^{A_t}$ by $Q_t$. The main observation is that whoever is losing with $A_t$, can be assumed to add something from $Q_t$ to $A$. This is because in this game every move costs money, we want to move as little as possible; there's no point making a move until we're winning. But this also implies that if we're losing, there's no point adding anything from outside $Q_t$.

Assume for simplicity that $M$ runs for exactly $2n$ steps and at steps $2i$ and $2i+1$ it queries a word of length exactly $i$. The cost function $f$ will simply be $2^{-i}$ on words of length $i$. The game will be such that Alice always needs to add odd length words and Bob always needs to add even length words to $A$. Suppose that $n$ is odd and initially Alice is losing.

The budgets $m_A$ and $m_B$ will be set so that she can choose exactly one of the length $n$ words queried by $M^{A_0}$ to be added to $A$. The game will be such that this makes her the winner, so Bob will have to move. Again due to budget constraints, he will have to choose exactly one of the length $n-1$ words queried by $M^{A_1}$ to be added to $A$. After any of these are added, $M^{A_2}$ will query two new length $n$ words (the same ones, regardless of what word Bob added to $A$), and Bob will win. Alice will be forced to add exactly one of these new length $n$ words to $A$ to make her win.

The game goes on in this manner, which can be imagined as following the branches of a complete binary tree of depth $n$, though at each branching node one of the players (determined which by the parity of the depth of the node) needs to make a choice about which word to add to $A$. After they go through the tree, they will run out of their budget. If at any stage of the game one of them decides to add some word that is shorter (e.g., Alice a length $k<n$ word from $Q_0$ in the first step), then if the other player (in our example Bob) just plays always the longest word he can in the binary tree, he will have some money left at the end and we make the game so that he can use this to win. (Note that Alice might also have some money left, but Bob will have more, so we design the end-game that if one of them has more money, then that player can win.)

This way Alice decides for exponentially many pairs of odd-length words, and Bob about exponentially many even-length words which one of each pair goes to $A$, and they make these choices in an alternating manner.

$\endgroup$
  • $\begingroup$ Thank you for your answer. I asked you some questions by e-mail. $\endgroup$ – Alexey Milovanov Oct 30 '18 at 8:03

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.