Descriptive Complexity of Deterministic Polylogarithmic Time

Flavio Ferrarotti, Senén González, José Maria Turull Torres, Jan Van den Bussche, Jonni Virtema

TL;DR

This paper introduces "index logic," a novel two-sorted logic designed to precisely capture the computational power of deterministic polylogarithmic time (PolylogTime). By providing a logical framework for these efficient computations, the authors offer a new perspective on understanding and characterizing problems solvable within this complexity class.

What Problem Does This Paper Address?

The field of descriptive complexity aims to find logical systems that precisely mirror computational complexity classes. For instance, existential second-order logic captures NP, and fixed-point logic captures P on ordered structures. However, a natural and practically relevant complexity class, deterministic polylogarithmic time (PolylogTime), which describes computations like binary search, lacked a corresponding logical characterization. This paper addresses this gap by developing a new logic, "index logic," specifically tailored to capture PolylogTime.

Methods

The core contribution is the introduction of index logic, a two-sorted logic. One sort ranges over the elements of the input structure, while the other ranges over bit positions used to address these elements. This separation is key to handling the efficiency of polylogarithmic time. The logic incorporates fixed-point operators and a novel "indexing mechanism" that binds variables based on bit positions.

To prove their logic captures PolylogTime, the authors also introduce a variant of random-access Turing machines that can directly access relations and functions of a structure, rather than just a single encoded input string. They demonstrate the equivalence of this direct-access model with the standard random-access model for PolylogTime computations.

Datasets

Not discussed in the paper. The paper focuses on theoretical characterizations of complexity classes using logical systems and Turing machine models, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Index Logic for PolylogTime: The creation of index logic provides a formal logical language that precisely matches the computational power of deterministic polylogarithmic time. This is a significant step in descriptive complexity.
  • Two-Sorted Logic with Bit Positions: The novel use of a second sort for bit positions is crucial for logically representing the efficient, address-based access characteristic of polylogarithmic time computations.
  • Direct-Access Turing Machines: The introduction of a direct-access Turing machine model simplifies proofs by allowing direct interaction with structure components, proving equivalent in expressive power to standard random-access machines for PolylogTime.
  • Order Predicate Necessity: The paper investigates whether an explicit order predicate on the domain is essential for index logic to capture PolylogTime, finding it is necessary when dealing with constant symbols.
  • PolylogSpace Characterization: The paper also extends its framework to polylogarithmic space (PolylogSpace) by introducing a variant of index logic with partial fixed-point operators.

Key Results

  • Index Logic Captures PolylogTime: The paper proves that index logic precisely characterizes the complexity class PolylogTime over ordered finite structures.
  • Index Logic with Partial Fixed Points Captures PolylogSpace: A variant of index logic with partial fixed-point operators is shown to capture the complexity class PolylogSpace.
  • Equivalence of Turing Machine Models: Both standard random-access Turing machines and a new direct-access Turing machine model are shown to be equivalent for defining PolylogTime.
  • Order Predicate's Role: The paper demonstrates that for structures with constant symbols, the built-in order predicate is necessary for index logic to capture PolylogTime.

Limitations and Future Work

  • Order-Invariant Queries: A key open problem highlighted is finding a logical characterization for order-invariant queries computable in PolylogTime. This is challenging because index logic is inherently tied to ordered structures.
  • RAM Model Integration: The authors suggest exploring a RAM model that operates directly on structures, potentially leading to equivalent PolylogTime notions.
  • Extending Index Logic: They propose that extending index logic with numeric variables that can hold polynomial values and arbitrary polynomial-time functions could serve as useful syntactic sugar without increasing expressive power.

Summary updated

Abstract

We propose a logical characterization of problems solvable in deterministic polylogarithmic time ($$\mathrm {PolylogTime}$$). We introduce a novel two-sorted logic that separates the elements of the input domain from the bit positions needed to address these elements. In the course of proving that our logic indeed captures $$\mathrm {PolylogTime}$$ on finite ordered structures, we introduce a variant of random-access Turing machines that can access the relations and functions of the structure directly. We investigate whether an explicit predicate for the ordering of the domain is needed in our logic. Finally, we present the open problem of finding an exact characterization of order-invariant queries in $$\mathrm {PolylogTime}$$.
BibTeX
@inproceedings{ferrarotti2019descriptive,
  author = {Flavio Ferrarotti and Senén González and José Maria Turull Torres and Jan Van den Bussche and Jonni Virtema},
  title = {{Descriptive Complexity of Deterministic Polylogarithmic Time}},
  booktitle = {WoLLIC},
  year = {2019},
  doi = {10.1007/978-3-662-59533-6\_13},
}
Figure