On Existential MSO and its Relation to ETH

D 2016

On Existential MSO and its Relation to ETH

GANIAN, Robert, Ronald DE HAAN, Stefan SZEIDER a Iyad KANJ

Základní údaje

Originální název

On Existential MSO and its Relation to ETH

Autoři

GANIAN, Robert (203 Česká republika, garant, domácí), Ronald DE HAAN (528 Nizozemské království), Stefan SZEIDER (40 Rakousko) a Iyad KANJ (840 Spojené státy)

Vydání

Germany, 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26, od s. "42:1"-"42:14", 14 s. 2016

Nakladatel

Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Kód RIV

RIV/00216224:14330/16:00093950

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-016-3

ISSN

DOI

http://dx.doi.org/10.4230/LIPIcs.MFCS.2016.42

Klíčová slova anglicky

algorithms; logic; exponential time hypothesis

Štítky

core_A, firank_A

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 27. 8. 2019 12:09, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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.

Citovat

GANIAN, Robert, Ronald DE HAAN, Stefan SZEIDER a Iyad KANJ. On Existential MSO and its Relation to ETH. Online. In Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier. 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26. Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016, s. "42:1"-"42:14", 14 s. ISBN 978-3-95977-016-3. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.MFCS.2016.42.

@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 a 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, s.~''42:1''-''42:14'', 14 s. ISBN~978-3-95977-016-3. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.MFCS.2016.42.

Podrobný výpis o publikaci