4
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.