Skip to main content
Share Your Experience: Take the 2024 Developer Survey
19 votes
Accepted

For which regular expressions $\alpha$ is $\{ \beta \mid L(\alpha) = L(\beta) \}$ PSPACE-complete?

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)\...
David's user avatar
  • 308
13 votes

Is this variation of TQBF still PSPACE-complete?

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 ...
Lutfar Rahman Milu's user avatar
13 votes
Accepted

Does P = NP imply NP being a strict subset of PSPACE?

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 ...
D.W.'s user avatar
  • 12.1k
11 votes
Accepted

Is $PSPACE$ believed to be different than $PP$?

I hope someone with more knowledge can supply an additional answer. I don't have a reference or a survey*, but in my experience people expect that $\text{PP}\subsetneq \text{PSPACE}$, mostly because, ...
Lieuwe Vinkhuijzen's user avatar
9 votes
Accepted

What is the minimum complexity oracle that separates PSPACE from the polynomial hierarchy?

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 ...
Joshua Grochow's user avatar
7 votes

Have these coloring games been solved?

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 ...
Grapher's user avatar
  • 71
7 votes

is SUBEXP contained within PSPACE?, NP?

SUBEXP is neither known or widely believed to lie in PSPACE (and -- contrary to one of the comments -- this is not known to have any connection to SETH). It is not known whether the containment "...
Eric Allender's user avatar
7 votes
Accepted

How to prove $P^{Halt} = PSPACE^{Halt}$

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 ...
Dmytro Taranovsky's user avatar
6 votes
Accepted

Intersection Non-Emptiness for Two-Way Finite Automata

Unlike one-way models, intersection of 2-way NFAs is "cheap": Given 2-way NFAs $A_1,A_2$, you can construct a 2-way NFA $B$ for their intersection that works as follows: it first behaves ...
Shaull's user avatar
  • 5,646
6 votes
Accepted

Quantum complexity of TQBF

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 ...
Ryan Williams's user avatar
6 votes
Accepted

Does there exist an oracle $A$ such that $(P^{\#P})^{A} \neq PSPACE^{A}$?

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 ...
Markus Bläser's user avatar
5 votes

What are consequences of the collapse of CH?

You could also ask similar questions about the polynomial hierarchy. The consensus in the research community is that PH is unlikely to collapse ... but I can't think of any dramatic consequences that ...
Eric Allender's user avatar
4 votes
Accepted

Does Rush-Hour (or Klotski) admit a search-to-decision reduction?

Yes! As long as we can give the oracle a limit on the number of steps in a path, I think we can do it this way: Set $k\leftarrow n^3$ and set $B\leftarrow B_0$, where $B_0$ is the initial ...
wobtax's user avatar
  • 96
3 votes
Accepted

Consequences of a distillation algorithm for PSPACE

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\...
Michael Lampis's user avatar
3 votes

How hard is Hex from a symmetric position?

Finding a winning move in symmetric positions in Hex is PSPACE-complete First, let's define our problem, and call it SYMHEXMOVE: Take as an input: a symmetric Hex position Output: any move which is ...
Kevin Wang's user avatar
3 votes

Why $PSPACE!=Dtime(2^n)$?

If DTIME(2^n)=PSPACE then DTIME(2^poly)=PSPACE. But, by the time hierarchy theorem, DTIME(2^n)⊊DTIME(2^poly)
Avi Tal's user avatar
  • 1,606
2 votes

Why is it a mystery if PSPACE ?= EXPTIME?

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. ...
Dmitri Urbanowicz's user avatar
2 votes

Evidence for $\mathsf{P} \neq \mathsf{PP}$ if the polynomial hierarchy collapses?

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 ...
Joshua Grochow's user avatar
1 vote
Accepted

Which 1-player games are EXPTIME-complete? Also, are there any known games that are EXPSPACE-complete?

From the comments, the desiderata are: Preferably, a game that is/was in play by some human population (as opposed to one whose rules were written to have it fall in the complexity class that I am ...
Kevin Wang's user avatar
1 vote
Accepted

Quantum complexity of TQBF with an untrusted oracle

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)$,...
Geoffrey Irving's user avatar
1 vote
Accepted

Does $\exists\mathbb{R}=\mathbf{PSPACE}$?

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 ...
Bjørn Kjos-Hanssen's user avatar

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