Descriptive complexity of deterministic polylogarithmic time and space

We propose logical characterizations of problems solvable in deterministic polylogarithmic time (PolylogTime) and polylogarithmic space (PolylogSpace). We introduce a novel two-sorted logic that separates the elements of the input domain from the bit positions needed to address these elements. We pr...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer and system sciences 2021-08, Vol.119, p.145-163
Main Authors: Ferrarotti, Flavio, González, Senén, Turull Torres, José María, Van den Bussche, Jan, Virtema, Jonni
Format: Article
Language:English
Subjects:
Descriptive complexity
Polylogarithmic queries
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We propose logical characterizations of problems solvable in deterministic polylogarithmic time (PolylogTime) and polylogarithmic space (PolylogSpace). We introduce a novel two-sorted logic that separates the elements of the input domain from the bit positions needed to address these elements. We prove that the inflationary and partial fixed point variants of this logic capture PolylogTime and PolylogSpace, respectively. In the course of proving that our logic indeed captures PolylogTime on finite ordered structures, we introduce a variant of random-access Turing machines that can access the relations and functions of a structure directly. We investigate whether an explicit predicate for the ordering of the domain is needed in our PolylogTime logic. Finally, we present the open problem of finding an exact characterization of order-invariant queries in PolylogTime.
ISSN:0022-0000
1090-2724
DOI:10.1016/j.jcss.2021.02.003