Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2410.04117 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914140846555136 |
|---|---|
| author | Yamakami, Tomoyuki |
| author_facet | Yamakami, Tomoyuki |
| contents | Syntactic NL or succinctly SNL was first introduced in 2017, analogously to SNP, as a ``syntactically''-defined natural subclass of NL (nondeterministic logarithmic-space complexity class) 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 to achieve the better understandings of logical expressibility in NL. For instance, SNL does not enjoy the dichotomy theorem unless L=NL. To express the ``complementary'' problems of SNL problems logically, we introduce $μ$SNL, which is an extension of SNL by allowing the use of $μ$-terms. As natural variants of SNL, we further study the computational complexity of monotone and optimization versions of SNL, respectively called MonoSNL and MAXSNL. We further consider maximization problems that are logarithmic-space approximable with only constant approximation ratios. We then introduce a natural subclass of MAXSNL, called MAX$τ$SNL, which enjoys such limited approximability. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_04117 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Logical Expressibility of Syntactic NL for Complementarity, Monotonicity, and Maximization Yamakami, Tomoyuki Computational Complexity Syntactic NL or succinctly SNL was first introduced in 2017, analogously to SNP, as a ``syntactically''-defined natural subclass of NL (nondeterministic logarithmic-space complexity class) 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 to achieve the better understandings of logical expressibility in NL. For instance, SNL does not enjoy the dichotomy theorem unless L=NL. To express the ``complementary'' problems of SNL problems logically, we introduce $μ$SNL, which is an extension of SNL by allowing the use of $μ$-terms. As natural variants of SNL, we further study the computational complexity of monotone and optimization versions of SNL, respectively called MonoSNL and MAXSNL. We further consider maximization problems that are logarithmic-space approximable with only constant approximation ratios. We then introduce a natural subclass of MAXSNL, called MAX$τ$SNL, which enjoys such limited approximability. |
| title | Logical Expressibility of Syntactic NL for Complementarity, Monotonicity, and Maximization |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2410.04117 |