# 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 ?

## 1 Answer

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.

Update: I'd be glad to take into account the downvoter's opinion and improve the answer.

• Pay your attention that my graph has exponential size so DFS is not good choice. Even if it is ok (because I don't understand something) - what about approach with non-determinism ? – Haskell Fun Jul 24 '17 at 21:52
• 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
• Can you fix your comment to show me latex expressions. And again - what about approach with non-determinism ? – Haskell Fun Jul 24 '17 at 21:56
• You could use also a nondeterministic TM since NPSPACE = PSPACE, but that is redundant. Just check using the same algorithm on a nondet TM. – fade2black Jul 24 '17 at 21:59
• @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