# Tag Info

37

It is an Unordered Constraint Satisfaction game and it is PSPACE-complete and it has been proved to be PSPACE-complete only recently; a proof can be found in: Lauri Ahlroth and Pekka Orponen, Unordered Constraint Satisfaction Games. Lecture Notes in Computer Science Volume 7464, 2012, pp 64-75. Abstract: We consider two-player constraint satisfaction ...

30

It may also be worthwhile to note that this problem was also solved in the 70's by Thomas Schaefer in ￼Complexity of decision problems based on finite two-person perfect-information games. In fact, he proves a slightly stronger result in that the language remains PSPACE-complete even when restricted to positive CNF formulas.

17

This question is addressed in Section 2 of [1], which shows (Theorem 2.6) that the problem is in P if $L(\alpha)$ is finite; coNP-complete if $L(\alpha)$ is infinite but bounded (i.e. $L(\alpha)\subseteq w_1^*w_2^*\ldots w_k^*$ for some $w_1,\ldots, w_k$); PSPACE-complete otherwise. [1] Harry B. Hunt, Daniel J. Rosenkrantz, Thomas G. Szymanski, On the ...

13

No. It is possible (as far as we know) that $\textbf{P} = \textbf{NP} = \textbf{PSPACE}$. If $\textbf{P} = \textbf{NP}$, the polynomial hierarchy collapses, i.e., $\textbf{P} = \textbf{PH}$. See also Can one amplify P=NP beyond P=PH? for an attempt to understand the limits of the implications of $\textbf{P} = \textbf{NP}$, and see Why doesn't P=NP ...

12

We proved that this game is PSPACE-complete for 5-CNFs but has Linear Time algorithm for 2-CNFs. The previous best result was Ahlroth and Orponen's 6-CNFs. You can find the conference paper at ISAAC 2018. **Update: Nov, 16, 2019 We proved that the game is tractable for 3-CNFs under some restrictions on 3-CNFs. We also radically conjectured that this game is ...

10

Undirected (Vertex) Geography is in P. In particular, the game on graph $G$ with starting vertex $v$ is a win for player 1 if and only if every maximum matching of $G$ uses the vertex $v$. This can be checked in polynomial time. The above is Theorem 1.1 from the paper "Undirected Edge Geography", by Fraenkel, Scheinerman and Ullman, Theoretical Computer ...

9

I believe if you trace through the argument given, e.g., in Section 4.1 of Ker-I Ko's survey, you get an upper bound of $\mathsf{DTIME}(2^{2^{O(n^2)}})$. In fact, we can replace $n^2$ here with any function $nf(n)$ where $f(n) \to \infty$ as $n \to \infty$. This isn't quite what was asked for, but it's close. In particular, using the translation between ...

7

Perhaps a fairly natural game is the following: Player 1 is placed in the middle of a maze and must reach the exit in order to win. Player 2 is in the same maze and must collect a set of "components" to build a radio controller that lets him close the exit (and win). Deciding the next move from a winning position is easy for Player 1: just follow the ...

6

The best quantum algorithm for QBF on n variable formulas of size s runs in about $2^{n/2}poly(s)$ steps, regardless of quantifier alternations. This is due to a series of advances on quantum algorithms for game tree search in the early 2000s. Here is the first reference I found from googling; there are more: https://arxiv.org/abs/0907.1623

6

On popular request, here is my comment as an answer: There is an oracle separating $\mathrm{PP}$ from $\mathrm{PSPACE}$: Jacobo Toran, A combinatorial technique for separating counting complexity classes, ICALP 1989. The best result for $\mathrm{P}^\mathrm{PP}$ that I know is a conditional result by Heribert Vollmer: Relating polynomial time to constant ...

6

Finding the answer to your question is not overly difficult, if one is used to proving PSPACE upper bounds. But I think one cannot find an answer to your question in the literature, so here it is: Given a regular expression r of alphabetic width n, i.e. with n alphabetic letters, you can enumerate all regular expressions of alphabetic width 1,2,3, one by ...

5

The answer is yes, for the first game you list! This result was only established in 2019. Here is a link to the paper: Costa et al. 2019 Even more recently, some variants of the first game were proved to be PSPACE-complete. This result can be found here: Marcilon et al. 2019.

4

The main difference between time and space is that you can reuse space that is not needed anymore. If you return from the recursive call that evaluates $A$, you can reuse the space used by this computation to compute the value of $B$. Because of this you only need to store one branch of the decision tree of the original QBF formula in memory, which gives ...

4

By your constraints, we also have the stronger opposite relation: if POSITION-COMPLEXITY is in a class $C$, then so is MOVE-COMPLEXITY, since it suffices to test the finite number of available moves. (I assumed by "finite" you meant "constant", if it is arbitrary then the complexity might change). Then it suffices to look at some natural games where ...

3

Using $n$ calls to the halting oracle and time $O(n^2)$, you can compute the first $n$ bits of the Chaitin's constant. Using the $n$ bits of the Chaitin's constant and unbounded time, all queries to the halting oracle of length approximately $≤n$ (depending on the representation) can be eliminated. Finally, the result can be obtained in bounded time by ...

3

If DTIME(2^n)=PSPACE then DTIME(2^poly)=PSPACE. But, by the time hierarchy theorem, DTIME(2^n)⊊DTIME(2^poly)

3

An answer to the first question can be found in a paper by Schaefer and Umans, Completeness in the polynomial-time hierarchy: A compendium (2002). In subsection "Coding and cryptology" (see p. 24), two $\Pi_2^p$-complete problems appear: checking an upper bound on the covering radius of a linear code, and deciding whether a linear code is $r$-identifying ($... 3 Theorem 15.3 of the recent "Parameterized Algorithms" textbook by Cygan et al. states the following: "Let$L, R ⊆ \Sigma^*$be two languages. If there exists an OR-distillation of L into R, then$L\in coNP / poly$" So, I think that if there exists an OR-distillation from a PSPACE-complete language$L$to itself, then$PSPACE \subseteq coNP/poly$, i.e. not ... 2 It sounds like this paper has some of what you're looking for: http://arxiv.org/abs/1202.5762 The general form of the first question is a really simple reduction: using colors {0, ..., n-1}, start with a Node Kayles instance and create a vertex for each of the colors from 1 to n-1 and connect them to each uncolored vertex. Now those colors can't be played ... 2 In fact, in the so-called Picker-Chooser or Chooser-Picker games it is easy to construct examples for which one player's best strategy is a simple pairing strategy, while the other has to solve a 3-SAT on any CNF specified before, that is an NP-complete problem. Say, a Picker-Chooser games is an asymmetric game on an hypergraph H=(V, E): Picker picks two ... 2 As there is no answer yet, I turn my comment to answer, Marathe et al. in their ICALP93 paper, defined some problems which are PSPACE complete but they admit constant factor approximations, they also provide some inapproximability results. For this particular question, consider MAX3SAT, corresponding decision problem is PSPACE-complete even if the ... 2 Another quick way to prove the Metatheorem 2c (PSPACE-hardness when the doors are controlled by two plates) is to use the Nondeterministic Constraint Logic framework (R.A. Hearn and E.D. Demaine, The Nondeterministic Constraint Logic Model of Computation: Reductions and Applications). In this case it is sufficient to use an horizontal series of vertical ... 2 Perhaps you can easily simulate a LBA; the idea is the following: for every cell of the LBA tape add a cell gadget$G_i$that can be entered only from the bottom and leaved only from the top; the gadget has an entrance door$C_i$which simulates the head position (only one$C_i$is opened at every step); then there are two bit doors$Z_i$and$O_i$;$Z_i$... 2 Query the oracle to solve$K$. Since we've assumed that$PSPACE = EXPTIME$, the answer must therefore fit in polynomial space; so it will only take polynomial time to write the answer to the tape. You are talking about decision problems. They only have yes and no answers, which you can write down quickly regardless of relationships between complexity ... 2 The scaled down version of$\mathsf{PH}$versus$\mathsf{PP}$is$\mathsf{AC}^0$versus$MAJ \circ \mathsf{AC}^0$, and we know that for the latter there is an exponential separation. Of course, this separation doesn't propagate exponentially up, but you could take this as philosophical evidence that$\mathsf{PH}$is different enough from$\mathsf{PP}$that ... 1 This question is more complicated to state than its predecessor Quantum complexity of TBQF, but in hindsight it is also way easier to answer. Theorem: The complexity is$\tilde{O}\left(2^{n/4}\right)$, using a single call to Grover's algorithm to check if there is a path falsifying the oracle. Moreover, this is optimal in the black box case. Consider a TBQF ... 1 The issue may be whether or not Schwartz and Sharir show that motion plan existence is many-one polynomial time reducible to$\exists\mathbb R$. If they need several queries to$\exists\mathbb R\$ for a given motion plan existence instance, then that's not a many-one reduction.

Only top voted, non community-wiki answers of a minimum length are eligible