Descriptive complexity of deterministic polylogarithmic time

Authors Flavio Ferrarotti
Senén Andrés González Cornejo
José María Turull Torres
Jan Van den Bussche
Jonni Virtema
Title Descriptive complexity of deterministic polylogarithmic time
Booktitle Logic, Language, Information, and Computation - Proc. WoLLIC 2019
Type in proceedings
Publisher Springer
Series Lecture Notes in Computer Science
Volume 11541
ISBN 978-3-662-59532-9
DOI 10.1007/978-3-662-59533-6_13
Month July
Year 2019
Pages 208-222
SCCH ID# 19106

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.