Descriptive complexity of deterministic polylogarithmic time

Autoren Flavio Ferrarotti
Senén Andrés González Cornejo
José María Turull Torres
Jan Van den Bussche
Jonni Virtema
Titel Descriptive complexity of deterministic polylogarithmic time
Buchtitel Logic, Language, Information, and Computation - Proc. WoLLIC 2019
Typ in Konferenzband
Verlag Springer
Serie Lecture Notes in Computer Science
Band 11541
ISBN 978-3-662-59532-9
DOI 10.1007/978-3-662-59533-6_13
Monat July
Jahr 2019
Seiten 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.