Abstract / Description of output
The L L=?NL NL question remains one of the major unresolved problems in complexity theory. Both L and NL have logical characterizations as the sets of ordered structures expressible in first-order logic augmented with the appropriate Transitive Closure operator [I87]: Over ordered structures, (FO + DTC) captures L and (FO + TC) captures NL. On the other hand, in the absence of ordering, (FO + TC) is strictly more powerful than (FO + DTC) [GM92]. An apparently quite different “structured” model of logspace machines is the Jumping Automaton on Graphs (JAG), [CR80]. We show that the JAG model is intimately related to these logics on “locally ordered” structures. We argue that the usual JAG model is unreasonably weak and should be replaced, wherever possible, by the two-way JAG model, which we define. Furthermore, we have shown that the language (FO + DTC) over two-way locally ordered graphs is more robust than even the two-way JAG model, and yet lower bounds remain accessible. We prove an upper bound on the power of TC over locally ordered graphs, and three lower bounds on DTC.
| Original language | English |
|---|---|
| Title of host publication | STACS 94, 11th Annual Symposium on Theoretical Aspects of Computer Science, Caen, France, February 24-26, 1994, Proceedings |
| Publisher | Springer |
| Pages | 123-135 |
| Number of pages | 13 |
| Volume | 775 |
| ISBN (Electronic) | 978-3-540-48332-8 |
| ISBN (Print) | 978-3-540-57785-0 |
| DOIs | |
| Publication status | Published - 1994 |