Universal Traversal Sequences
Joan Feigenbaum, Nick Reingold · American Mathematical Monthly · 1994
this article we discuss a purely combinatorial problem, the construction of short universal traversal sequences, and its relationship to questions about logspace computation. We state the problem formally, show how it arises naturally in complexity theory, and review some of the known partial results. A basic introduction to complexity theory can be found in [6]. The P vs. NP problem is recognized by the mathematical world as the central open question in the theory of computation. Less widely known outside of computer science is the fact that the analogous question for space-bounded computation was resolved long ago