Timeline for Questions on unification theory (and its application to DAG isomorphism )
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 14, 2012 at 15:24 | comment | added | Emil Jeřábek | Actually, now that I think about it, the NL-algorithm I sketched above does work for bisimulation, but I’m not sure how to make it decide isomorphism, even for ordered DAGs. | |
| Feb 14, 2012 at 15:08 | comment | added | Emil Jeřábek | ... This gives only an alternating logspace algorithm, which is useless as alternating logarithmic space equals deterministic polynomial time, and we already know the problem is poly-time solvable. | |
| Feb 14, 2012 at 15:06 | comment | added | Emil Jeřábek | Well, yes, s-t-connectivity for DAG is a canonical NL-complete problem, but now I don’t quite see how to reduce it to DAG isomorphism. As for an upper bound, it is easy to see that (bisimulation as well as) isomorphism of (coloured) ordered rooted DAGs is in NL (follow nondeterministically parallel paths through both graphs until hitting a vertex with mismatched out-degree and/or colour). However, for unordered DAGs I would need to interleave these existential nondeterministic choices with universal nondeterministic choices over the successors of the given node. ... | |
| Feb 11, 2012 at 4:57 | comment | added | SigmaX | Ah, I happen to have come across it tonight in Sipser, Introduction to the Theory of Computation, 2nd ed. tonight: determining the existence of a path from nodes s to t in a DAG is NL-complete. This appears to me necessary to compute DAG isomorphism. | |
| Feb 7, 2012 at 19:25 | comment | added | Emil Jeřábek | Sorry, I can’t recall how I meant it to work. I suppose I shouldn’t answer technical questions right after returning from a New Year party. | |
| Feb 6, 2012 at 2:12 | comment | added | SigmaX | Can you provide a source or proof? When I try to google "DAG isomorphism NL-complete" I get this thread! | |
| Jan 1, 2012 at 1:46 | comment | added | SigmaX | Technically it would be O(n^2 + ne), since DFS is O(n + e), with n = number of vertices and e = number of edges. By "rooted DAG" I mean that all nodes are reachable from the root. I suppose this means I lose generality. It'd still take a bit to convince me that the worst-case complexity is greater than O(n^3 + n^2e), however. | |
| Jan 1, 2012 at 1:26 | history | answered | SigmaX | CC BY-SA 3.0 |