# Tag Info

Accepted

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

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

### 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)

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

### 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 ...
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 ...
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)$,...
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 ...

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