Logical Expressibility of Syntactic NL for Complementarity and Maximization

In a discussion on the computational complexity of “parameterized” NL (nondeterministic logarithmic-space complexity class), Syntactic NL or succinctly SNL was first introduced in 2017 as a “syntactically”-defined natural subclass of NL using a restricted form of second-order logic in close connection to the so-called linear space hypothesis. We further explore various properties of this complexity class SNL. In particular, we consider the expressibility of “complementary” problems of SNL problems. As a variant of \(\textrm{SNL}\) , we also study an optimization version of SNL, called MAXSNL, and its natural subclass, called MAX \(\tau \) SNL.