Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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}$.
