Descriptive complexity of deterministic polylogarithmic time

F. Ferrarotti, S. González Cornejo, J. Turull Torres, J. Van den Bussche, J. Virtema. Descriptive complexity of deterministic polylogarithmic time. volume 11541, pages 208-222, DOI 10.1007/978-3-662-59533-6_13, 7, 2019.

Autoren
  • Flavio Ferrarotti
  • Senén Andrés González Cornejo
  • José María Turull Torres
  • Jan Van den Bussche
  • Jonni Virtema
BuchLogic, Language, Information, and Computation - Proc. WoLLIC 2019
TypIn Konferenzband
VerlagSpringer
SerieLecture Notes in Computer Science
Band11541
DOI10.1007/978-3-662-59533-6_13
ISBN978-3-662-59532-9
Monat7
Jahr2019
Seiten208-222
Abstract

We propose a logical characterization of problems solvable in deterministic polylogarithmic time (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 PolylogTimePolylogTime 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 PolylogTime.