# What class this graph connectivity problem belong to

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?

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