# Show that problem is PSPACE-complete - path in directed graph

I have a following problem:
Given $n$ and graph of size $2^n$, and circuit with $2n$ input gates. Directed edge between $k$ and $l$ exists iff only and only we encode $k$ and $l$ as bits and launch circuit on this input and get result $0$.

Problem: Is there exists path from vertex $k$ to vertex $l$ ?

I can reduce arbitrary problem from $PSPACE$ to above problem. The only thing that I can't do is showing that problem given in exercies belongs to PSPACE.

Tell me please, if my reasoning is correct (it seems to be too simple):
We know that $PSPACE = NPSPACE$. So we can give non-determinitic algorithm. Algorithm can guess sequentially verticles and check (using circuit) if there exists path).
I can say more, let algorithm guess ansewr (0 or 1).

Can you help me ?

Given $k$ and $l$ you can check if there is a path between these nodes using DFS. DFS requires polynomial space and time. So, that problem is in PSPACE.
• You should measure the complexity in terms of input size . Your input size is $2^n$ not $n$. – fade2black Jul 24 '17 at 21:55
• @fade2black The OP says the graph is determined by the number of vertices ($n$ bits) and a circuit (whose size is $O(n)$) which determines whether two vertices are adjacent. There is no need to include a list of vertices or adjacency matrix in the input. – stewbasic May 9 '18 at 6:01