The Polylog-Time Hierarchy Captured by Restricted Second-Order Logic
Flavio Antonio Ferrarotti, Senén González, Klaus‐Dieter Schewe, José María Turull-Torres · 2018
Let SOplogdenote the restriction of second-order logic, where second-order quantification ranges over relations of size at most poly-logarithmic in the size of the structure. In this article we investigate the problem, which Turing machine complexity class is captured by Boolean queries over ordered relational structures that can be expressed in this logic. For this we define a hierarchy of fragments Σmplog(and Πmplog) defined by formulae with alternating blocks of existential and universal second-order quantifiers in quantifier-prenex normal form. We first show that the existential fragment Σ1plogcaptures npolylog, i.e. the class of Boolean queries that can be accepted by a non-deterministic Turing machine with random access to the input in time O((log n)k) for some k ≥ 0. Using alternating Turing machines with random access input allows us to characterize also the fragments Σmplog(and Πmplog) as those Boolean queries with at most m alternating blocks of second-order quantifiers that are accepted by an alternating Turing machine. Consequently, SOplogcaptures the whole poly-logarithmic time hierarchy. We demonstrate the relevance of this logic and complexity class by several problems in database theory.