2
$\begingroup$

We are given a Boolean circuit $C(x_1, \dots, x_n,y_1, \dots, y_n)$ with $2n$ inputs and we have to determine if the graph $G_C = (V_C, E_C)$ (specified below) is connected: $$V_C = \{0,1\}^n, \\ E_C = \{((a_1, \dots, a_n), (b_1, \dots, b_n)) : C(a_1, \dots, a_n,b_1, \dots,b_n) = 1\}.$$

To which class this problem belongs? I know that graph connectivity can be done so fast (as fast as to be in P) and using a small amount of space. Does this is different in this particular graph? Is this problem in P, EXP, PSPACE?

$\endgroup$
3
$\begingroup$

$G$ has $2^n$ vertices, and for any two vertices $v_i,v_j$ we can check whether $(v_i,v_j)\in E$ in polynomial time (since circuit value problem is in P). By executing DFS on $G$ from any vertex you can find out whether $G$ is strongly connected in $O(|V|+|E|)=O\left(2^{2n}\right)$ time, which puts your problem in $E$, as the circuit's description is of size $\Omega(n)$.

Your problem is PSPACE-hard. Given a machine $M$ which uses $\le n^c$ space and input $x$, denote by $G_x$ its computation graph, i.e. the graph whose vertices are all possible configurations using $\le |x|^c$ cells and $(C_i,C_j)\in E_{G_x}$ iff $C_i$ is followed by $C_j$ in the computation of $M$. Now adjust $G_x$ by adding edges from every vertex to $C_x$, the initial configuration of $M$ on input $x$, and from the accepting configuration $C_{acc}$ (assume without loss of generality that it's unique) to all other vertices. Clearly this new graph $G_x'$ is strongly connected iff there is a path from the from $C_x$ to $C_{acc}$ in $G_x$. Given $M,x$ you can construct in polynomial time a circuit $C_{G_x'}$ that takes two vertices $C_i,C_j$ of $G_x'$ and outputs 1 iff there is an edge from $C_i$ to $C_j$ (checking whether one configuration is immediately followed by another is easy). I leave it to you to complete the details here.

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