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)\...
- 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 ...
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 ...
- 11.7k
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, ...
- 1,934
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 ...
- 36.9k
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 ...
- 2,537
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 ...
- 71
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 ...
- 27.3k
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 ...
- 2,878
4
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 ...
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\...
- 3,416
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 ...
- 156
3
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 "...
- 1,761
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)
- 1,596
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.
...
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 ...
- 36.9k
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 ...
- 156
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)$,...
- 3,243
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 ...
- 4,475
Only top scored, non community-wiki answers of a minimum length are eligible