Hot answers tagged

35

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 ...


28

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 ...


14

(An earlier version of this question asked if anyone has shown Portal 2 to be NP-hard.) Yes, someone has done this. Portal 2 is at least NP-hard. My friend created a proof-of-concept map showing that the ability to beat a Portal 2 level implies the ability to solve 3SAT instances: http://steamcommunity.com/sharedfiles/filedetails/?id=73499175


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 ...


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 ...


10

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

I think you could show it PSPACE-hard fairly easily, as there are doors controlled by pressure switches. I'm not sure exactly what the limitations of the level design are in Portal so this may not be quite right. (As I recall most levels have one door and one switch, which is not sufficient). The HalfLife 2 engine in general seems certainly capable of ...


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 ...


9

I think that this definition is nowadays known under the term space-constructible function. There are functions in sublogarithmic space that are space constructible, while others are not. http://dl2.acm.org/citation.cfm?id=31171 Andrzej Szepietowski: There are no fully space constructible functions between log log n and log n. Information Processing ...


7

$\mathrm{CSL}=\mathrm{NSPACE}(O(n))$. Thus, take your favourite PSPACE-complete problem. If it is decidable in $\mathrm{NSPACE}(O(n))$ (for example, QBF is), you are done. Otherwise, introduce a polynomial amount of padding to make it so.


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

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 ...


5

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 ...


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 ...


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 ...


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 ...


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 ($...


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

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.


1

PSPACE proof attempt of Portal 2 by reduction from TQBF Application of section 2.2 of Gaming is a hard job, but someone has to do it! On portal 2. A direct proof of the statement: Given Portal 2 can you encode a TQBF in the game? We disallow portals in certain parts to simplify the proof since this is allowed in the game but, we will show that if all ...


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