Reachability and the Power of Local Ordering

Kousha Etessami, Neil Immerman

Research output: Contribution to journalArticlepeer-review

Abstract

The L NL question remains one of the major unresolved problems in complexity theory. Both L and NL have logical characterizations as the sets of totally ordered (⩽) structures expressible in first-order logic augmented with the appropriate Transitive Closure operator (Immerman, 1987): (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) (Grädel and McColm, 1992).

An apparently quite different “structured” model of logspace machines is the Jumping Automaton on Graphs (JAG), (Cook and Rockoff, 1980). We show that the JAG model is intimately related to these logics on “one-way locally ordered” (1LO) 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, the language (FO + DTC + 2LO) over two-way locally ordered (2LO) 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 one-way locally ordered graphs, and three lower bounds on DTC.
Original languageEnglish
Pages (from-to)261-279
Number of pages19
JournalTheoretical Computer Science
Volume148
Issue number2
DOIs
Publication statusPublished - 1995

Fingerprint

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

Cite this