# Non-existence of PSPACE-hard unary language

I'm trying to prove that unless $$\mathsf{P}=\mathsf{PSPACE}$$, there is no unary language which is $$\mathsf{PSPACE}$$-hard.

Assuming there is an unary language $$A$$ which is $$\mathsf{PSPACE}$$-hard, it doesn't seem reasonable to solve $$A$$ in polynomial time. How can this be proved then?

## 1 Answer

Suppose that $$A$$ is a unary PSPACE-hard language. We will show how to solve TQBF, a PSPACE-complete language, in polynomial time.

Recall that an instance of TQBF is a quantified formula of the form $$\psi = \exists x_1 \forall x_2 \exists x_3 \forall x_4 \ldots \phi(x_1,\ldots,x_n)$$, where $$\phi$$ is an arbitrary propositional formula. The instance is a Yes instance if the formula is valid.

We construct a binary tree which will represent the truth value of $$\psi$$. We do it level by level. Each vertex in the tree corresponds to a partial assignment of $$x_1,\ldots,x_n$$. At the root, we just write the empty assignment.

Suppose that we have constructed the $$i$$‘th level, where $$0 \leq i < n$$. We construct the $$(i+1)$$’th level as follows. For each vertex $$\alpha$$ on the $$i$$’th level, we add two children, $$\alpha \cup \{x_{i+1} = 0\}$$ and $$\alpha \cup \{x_{i+1} = 1\}$$. For each new vertex $$\beta$$, we consider the formula $$\psi_\beta = Q x_{i+2} \ldots \phi(\beta,x_{i+2},\ldots,x_n)$$. We apply the polytime reduction from TQBF to $$A$$ on $$\psi_\beta$$, obtaining a “truth value” $$t_\beta$$; note that there are only polynomial many possible values for $$t_\beta$$. These truth values may repeat; for each truth value $$t$$, we pick one vertex of that truth value (“live vertex”), and point all other vertices (“shadow vertices”) having the same truth value to that vertex; we won’t add new children to the shadow vertices in the next step.

After $$n$$ such steps, all the (polynomially many) leaves are labeled by complete truth assignments $$\gamma$$ to $$x_1,\ldots,x_n$$. We can evaluate $$\psi_\gamma$$ directly, and so obtain the real truth values of all live vertices on the $$n$$’th level, and deduce the real truth values of all shadow vertices on the $$n$$’th levels. From these we can deduce the real truth values of all live vertices on the $$(n-1)$$’th levels, and hence of all shadow vertices on that level; and so on. Eventually, we will find the truth value of $$\psi$$.

Since each level contains only polynomially many vertices, this algorithm runs in polynomial time. It follows that $$\mathsf{P}=\mathsf{PSPACE}$$.