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

 F. Ferrarotti, K. Schewe, J. Turull-Torres. A restricted second-order logic for non-deterministic poly-logarithmic time. Logic Journal of the IGPL, volume 28, number 3, pages 389-412, DOI 10.1093/jigpal/jzz078, 6, 2020. Autoren Flavio Ferrarotti Klaus-Dieter Schewe José María Turull-Torres Typ Artikel Journal Logic Journal of the IGPL Nummer 3 Band 28 DOI 10.1093/jigpal/jzz078 Monat 6 Jahr 2020 Seiten 389-412 Abstract We introduce a restricted second-order logic SOplogSOplog 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 SOplogSOplog correspond 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)O((log⁡n)k) for some k≥0k≥0⁠, 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 SOplogSOplog is too weak as to define a total order of the domain. Nevertheless, SOplogSOplog 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 SOplogSOplog 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.