1
$\begingroup$

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 ?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
-3
$\begingroup$

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.

Improve this answer
$\endgroup$
12
  • $\begingroup$ 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 ? $\endgroup$
    – Haskell Fun
    Jul 24, 2017 at 21:52
  • $\begingroup$ You should measure the complexity in terms of input size . Your input size is $2^n$ not $n$. $\endgroup$
    – fade2black
    Jul 24, 2017 at 21:55
  • $\begingroup$ Can you fix your comment to show me latex expressions. And again - what about approach with non-determinism ? $\endgroup$
    – Haskell Fun
    Jul 24, 2017 at 21:56
  • $\begingroup$ You could use also a nondeterministic TM since NPSPACE = PSPACE, but that is redundant. Just check using the same algorithm on a nondet TM. $\endgroup$
    – fade2black
    Jul 24, 2017 at 21:59
  • 1
    $\begingroup$ @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. $\endgroup$
    – stewbasic
    May 9, 2018 at 6:01

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.