ECCC-Report TR14-008https://eccc.weizmann.ac.il/report/2014/008Comments and Revisions published for TR14-008en-usMon, 20 Jan 2014 22:26:11 +0200
Paper TR14-008
| Space Complexity of the Directed Reachability Problem over Surface-Embedded Graphs. |
N. V. Vinodchandran
https://eccc.weizmann.ac.il/report/2014/008The graph reachability problem, the computational task of deciding whether there is a path between two given nodes in a graph is the canonical problem for studying space bounded computations. Three central open questions regarding the space complexity of the reachability problem over directed graphs are: (1) improving Savitch's $O(\log^2 n)$ space bound, (2) designing a polynomial-time algorithm with $O(n^{1-\epsilon})$ space bound, and (3) designing an {\em unambiguous} non-deterministic log-space (UL) algorithm. These are well-known open questions in complexity theory, and solving any one of them will be a major breakthrough. We will discuss some of the recent progress reported on these questions for certain subclasses of surface-embedded directed graphs.
Mon, 20 Jan 2014 22:26:11 +0200https://eccc.weizmann.ac.il/report/2014/008