A Restricted SecondOrder Logic for Nondeterministic PolyLogarithmic Time
Abstract
We introduce a restricted secondorder logic $\mathrm{SO}^{\mathit{plog}}$ for finite structures where secondorder quantification ranges over relations of size at most polylogarithmic in the size of the structure. We demonstrate the relevance of this logic and complexity class by several problems in database theory. We then prove a Fagin's style theorem showing that the Boolean queries which can be expressed in the existential fragment of $\mathrm{SO}^{\mathit{plog}}$ corresponds exactly to the class of decision problems that can be computed by a nondeterministic Turing machine with random access to the input in time $O((\log n)^k)$ for some $k \ge 0$, i.e., to the class of problems computable in nondeterministic polylogarithmic time. It should be noted that unlike Fagin's theorem which proves that the existential fragment of secondorder logic captures NP over arbitrary finite structures, our result only holds over ordered finite structures, since $\mathrm{SO}^{\mathit{plog}}$ is too weak as to define a total order of the domain. Nevertheless $\mathrm{SO}^{\mathit{plog}}$ provides natural levels of expressibility within polylogarithmic space in a way which is closely related to how secondorder logic provides natural levels of expressibility within polynomial space. Indeed, we show an exact correspondence between the quantifier prefix classes of $\mathrm{SO}^{\mathit{plog}}$ and the levels of the nondeterministic polylogarithmic time hierarchy, analogous to the correspondence between the quantifier prefix classes of secondorder logic and the polynomialtime hierarchy. Our work closely relates to the constant depth quasipolynomial size AND/OR circuits and corresponding restricted secondorder logic defined by David A. Mix Barrington in 1992. We explore this relationship in detail.
 Publication:

arXiv eprints
 Pub Date:
 November 2019
 arXiv:
 arXiv:1912.00010
 Bibcode:
 2019arXiv191200010F
 Keywords:

 Computer Science  Logic in Computer Science;
 Mathematics  Logic
 EPrint:
 Draft of Paper submitted to the Logic Journal of the IGPL. arXiv admin note: substantial text overlap with arXiv:1806.07127