Other formats:
BibTeX
LaTeX
RIS
@inproceedings{1376050,
author = {Ganian, Robert and de Haan, Ronald and Szeider, Stefan and Kanj, Iyad},
address = {Germany},
booktitle = {41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26},
doi = {http://dx.doi.org/10.4230/LIPIcs.MFCS.2016.42},
editor = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
keywords = {algorithms; logic; exponential time hypothesis},
howpublished = {elektronická verze "online"},
language = {eng},
location = {Germany},
isbn = {978-3-95977-016-3},
pages = {"42:1"-"42:14"},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
title = {On Existential MSO and its Relation to ETH},
year = {2016}
}
TY - JOUR
ID - 1376050
AU - Ganian, Robert - de Haan, Ronald - Szeider, Stefan - Kanj, Iyad
PY - 2016
TI - On Existential MSO and its Relation to ETH
PB - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
CY - Germany
SN - 9783959770163
KW - algorithms
KW - logic
KW - exponential time hypothesis
N2 - 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 paper, 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.
ER -
GANIAN, Robert, Ronald DE HAAN, Stefan SZEIDER and Iyad KANJ. On Existential MSO and its Relation to ETH. Online. In Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier. \textit{41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26}. Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016, p.~''42:1''-''42:14'', 14 pp. ISBN~978-3-95977-016-3. Available from: https://dx.doi.org/10.4230/LIPIcs.MFCS.2016.42.
|
