Problem Detail: I was studying nondeterministic Turing Machines and came across the following question: Describe a nondeterministic Turing Machine (NTM) that only accepts two graphs (G1 and G2) if they are isomorphic, and provide the NSPACE. The NTM should use as little space as possible. My attempt at answering this question goes something like this:
- If G1 and G2 have different no. of vertices and/or edges, reject
- Nondeterministically reorder the vertices v1 thru vn in G1. Leave G2 alone.
- Check if there is a bijection from G1 to G2, with the above vertex mapping. If so, accept.
At some point, the above algorithm will go thru all n! possible orderings of G1’s vertices, and will exhaustively check to see if there’s a bijection. Not quite sure what the NSPACE() value is, though, or how I would go about computing it. My guess is that re-ordering G1’s vertices v1 thru vn will take up n cells of the work tape, and checking every pair of vertices for bijection will require a small additional amount of space that can be reused for each subsequent pair? Or do we actually need to store all C(n, 2) pairs per graph? This is all very confusing, and I’m unsure whether I’m thinking thru this problem the right way. I’d appreciate any help.
Answered By : Ariel
Saying that at some point your algorithm goes through all $n!$ options is incorrect. You “guess” the permutation, and then check if it is an isomorphism, not just a bijection, the important condition you need to verify is $(u,v)in E_{G_1} iff left(f(u), f(v)right)in E_{G_2}$. You need to store the permutation (which requires $nlog n$ space, since keeping the index of a vertex in {v_1,…,v_n} requires $log n $ space). The verfication can reuse space, so you only need enough additonal space to find the permutations $f(u), f(v)$ for any edge $(u, v) in E_{G_1}$, and check if the corresponding edge exists in $G_2$. To find those you only need counters up to $n$, which can be saved in logarithmic space. Overall you used $O(nlog n)$ space. Note that you didn’t actually need the power of PSPACE here (didn’t do anything exponential), so this also proves $GIin NTIME(nlog n)$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/53766 Ask a Question Download Related Notes/Documents
Related
