D 2016

On Existential MSO and its Relation to ETH

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

Basic information

Original name

On Existential MSO and its Relation to ETH

Authors

GANIAN, Robert (203 Czech Republic, guarantor, belonging to the institution), Ronald DE HAAN (528 Netherlands), Stefan SZEIDER (40 Austria) and Iyad KANJ (840 United States of America)

Edition

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

Publisher

Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

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

Publication form

electronic version available online

RIV identification code

RIV/00216224:14330/16:00093950

Organization unit

Faculty of Informatics

ISBN

978-3-95977-016-3

ISSN

DOI

Keywords in English

algorithms; logic; exponential time hypothesis

Tags

Tags

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

Abstract

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.