A restricted second-order logic for non-deterministic poly-logarithmic time

DOI10.1093/JIGPAL/JZZ078MaRDI QIDQ5082331zbMATH OpenOpenAlexWikidataFDO

Authors Flavio Ferrarotti, Senén Gonzáles, Klaus-Dieter Schewe, Jose Maria Turull Torres

Publication date 16 June 2022

Published in Logic Journal of the IGPL (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.00010

zbMATH Keywords

descriptive complexityfinite modelspoly-logarithmic timesecond-order logic

Mathematics Subject Classification ID

Higher-order logic (03B16) Model theory of finite structures (03C13) Database theory (68P15) Descriptive complexity and finite models (68Q19)

Abstract: We introduce a restricted second-order logic $mathrm{SO}^{mathitplog}$ for finite structures where second-order quantification ranges over relations of size at most poly-logarithmic 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}^{mathitplog}$ corresponds exactly to the class of decision problems that can be computed by a non-deterministic Turing machine with random access to the input in time $O((logn{)}^k)$ for some $kge0$, i.e., to the class of problems computable in non-deterministic poly-logarithmic time. It should be noted that unlike Fagin's theorem which proves that the existential fragment of second-order logic captures NP over arbitrary finite structures, our result only holds over ordered finite structures, since $mathrm{SO}^{mathitplog}$ is too weak as to define a total order of the domain. Nevertheless $mathrm{SO}^{mathitplog}$ provides natural levels of expressibility within poly-logarithmic space in a way which is closely related to how second-order logic provides natural levels of expressibility within polynomial space. Indeed, we show an exact correspondence between the quantifier prefix classes of $mathrm{SO}^{mathitplog}$ and the levels of the non-deterministic poly-logarithmic time hierarchy, analogous to the correspondence between the quantifier prefix classes of second-order logic and the polynomial-time hierarchy. Our work closely relates to the constant depth quasipolynomial size AND/OR circuits and corresponding restricted second-order logic defined by David A. Mix Barrington in 1992. We explore this relationship in detail.

Recommendations

• A logical encoding of timed \(\pi\)-calculus
• scientific article; zbMATH DE number 1223631
• On expressive powers of timed logics: comparing boundedness, non-punctuality, and deterministic freezing
• A second-order system for polytime reasoning based on Grädel's theorem.
• A logic for PTIME and a parameterized halting problem
• scientific article; zbMATH DE number 1304315
• A Paraconsistent Linear-time Temporal Logic
• A logical characterization of timed (non-)regular languages
• Real-time logics: Complexity and expressiveness
• A restricted second order logic for finite structures

Cited in

(5)

• Descriptive complexity of deterministic polylogarithmic time and space
• \(\mathrm{SO}^F\): a semantic restriction over second-order logic and its polynomial-time hierarchy
• The Relational Polynomial-Time Hierarchy and Second-Order Logic
• A restricted second order logic for finite structures
• The logics for the complexity classes with limited non-determinism

This page was built for publication: A restricted second-order logic for non-deterministic poly-logarithmic time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5082331)