On Existential MSO and its Relation to ETH
| Autor: | Ronald de Haan, Stefan Szeider, Robert Ganian, Iyad A. Kanj |
|---|---|
| Přispěvatelé: | Logic and Computation (ILLC, FNWI/FGw), ILLC (FNWI) |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Discrete mathematics
Code (set theory) Class (set theory) 000 Computer science knowledge general works Exponential time hypothesis 010102 general mathematics 0102 computer and information sciences Computer Science::Computational Complexity 01 natural sciences Satisfiability Theoretical Computer Science TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Computational Theory and Mathematics Fragment (logic) 010201 computation theory & mathematics Dominating set Computer Science::Logic in Computer Science Computer Science Complexity class Feedback vertex set 0101 mathematics Mathematics |
| Zdroj: | ACM Transactions on Computation Theory, 12(4):22. Association for Computing Machinery (ACM) |
| ISSN: | 1942-3454 |
| Popis: | Impagliazzo et al. proposed a framework, based on the logic fragment defining the complexity class SNP, to identify problems that are equivalent to k -CNF- Sat modulo subexponential-time reducibility (serf-reducibility). The subexponential-time solvability of any of these problems implies the failure of the Exponential Time Hypothesis (ETH). In this article, we extend the framework of Impagliazzo et al. and identify a larger set of problems that are equivalent to k -CNF- Sat modulo serf-reducibility. We propose a complexity class, referred to as Linear Monadic NP, that consists of all problems expressible in existential monadic second-order logic whose expressions have a linear measure in terms of a complexity parameter, which is usually the universe size of the problem. This research direction can be traced back to Fagin’s celebrated theorem stating that NP coincides with the class of problems expressible in existential second-order logic. Monadic NP, a well-studied class in the literature, is the restriction of the aforementioned logic fragment to existential monadic second-order logic. The proposed class Linear Monadic NP is then the restriction of Monadic NP to problems whose expressions have linear measure in the complexity parameter. We show that Linear Monadic NP includes many natural complete problems such as the satisfiability of linear-size circuits, dominating set, independent dominating set, and perfect code. Therefore, for any of these problems, its subexponential-time solvability is equivalent to the failure of ETH. We prove, using logic games, that the aforementioned problems are inexpressible in the monadic fragment of SNP, and hence, are not captured by the framework of Impagliazzo et al. Finally, we show that Feedback Vertex Set is inexpressible in existential monadic second-order logic, and hence is not in Linear Monadic NP, and investigate the existence of certain reductions between Feedback Vertex Set (and variants of it) and 3-CNF-Sat . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|