Logical Expressibility of Syntactic NL for Complementarity, Monotonicity, and Maximization
<|reference_start|>Logical Expressibility of Syntactic NL for Complementarity, Monotonicity, 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 logical sentences, starting with second-order ``functional'' existential quantifiers followed by first-order universal quantifiers, 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 and introduce $\mu\mathrm{SNL}$, a variant of SNL by allowing the use of $\mu$-terms. As natural extensions of SNL, we further study the computational complexity of its monotone and optimization versions, respectively called MonoSNL and MAXSNL. While SNL does not enjoy the dichotomy theorem unless L$=$NL, we prove the dichotomy theorem for MonoSNL. We also consider a natural subclass of MAXSNL, called MAX$\tau$SNL, and show that all maximization problems in MAX$\tau$SNL are log-space approximable with only constant approximation ratios.<|reference_end|>
@article{yamakami2024logical,
    title={Logical Expressibility of Syntactic NL for Complementarity,
  Monotonicity, and Maximization},
    author={Tomoyuki Yamakami},
    journal={arXiv preprint arXiv:2410.04117},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.04117},
    primaryClass={cs.CC}
}