The logical complexity of queries on unordered graphs. Lindell, Steven, Ph.D. University of California,
A combinatorial problem can be viewed formally as a global property on finite relational structures. Such properties are called queries and can be defined syntactically by formulas composed from mathematical logic. In this dissertation, we study queries expressed in first-order logic and its extensions, and use this as a mathematical foundation on which to study some aspects of computational complexity.
Queries expressible explicitly in the language of first-order logic are called elementary in this study. An elementary translation is a bidirectional map between relational structures which can be defined by a sequence of elementary queries. Our first result is that all relational structures can be elementarily translated to directed graphs. This says that we may regard directed graphs as a universal unordered structure.
Inductive queries are obtained from elementary queries by recursive definition (with a least-fixed-point semantics). Immerman has shown that on finite structures with a total order of the domain, the inductive queries are precisely those computable in polynomial-time. But on unordered structures, there are simple polynomial-time queries which are not inductive (such as whether a number is even or odd). In previously known examples this was due to the fact that cardinalities cannot be determined inductively. We show that on the class of complete unordered binary trees (in which left and right children of a node are not distinguished), the inductive queries are strictly contained within the polynomial-time queries even though we can compute cardinality inductively. This implies that, in the absence of ordering, inductive plus the ability to measure size does not equal the power of polynomial time, and contributes new insight to the importance of ordering in the logical simulation of polynomial-time queries.
We define implicit queries by a second-order extension of elementary queries while still retaining a first-order semantics. Our last result shows that the implicit queries are exactly the queries computable in NP intersect co-NP, In particular, this provides a natural class of queries which is not enhanced by the presence of ordering.