Reachability and the Power of Local Ordering

Kousha Etessami, Neil Immerman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish
Title of host publicationSTACS 94, 11th Annual Symposium on Theoretical Aspects of Computer Science, Caen, France, February 24-26, 1994, Proceedings
PublisherSpringer Berlin Heidelberg
Number of pages13
ISBN (Electronic)978-3-540-48332-8
ISBN (Print)978-3-540-57785-0
Publication statusPublished - 1994


Dive into the research topics of 'Reachability and the Power of Local Ordering'. Together they form a unique fingerprint.

Cite this