Abstract
Impagliazzo et al. proposed a framework, based on the logic fragment defining the complexity class SNP, to identify problems that are equivalent to kCNFSat modulo subexponentialtime reducibility (serfreducibility). The subexponentialtime 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 kCNFSat modulo serfreducibility. 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 wellstudied 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 linearsize circuits, dominating set, independent dominating set, and perfect code. Therefore, for any of these problems, its subexponentialtime 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 3CNFSat.
BibTeX  Entry
@InProceedings{ganian_et_al:LIPIcs:2016:6455,
author = {Robert Ganian and Ronald de Haan and Iyad Kanj and Stefan Szeider},
title = {{On Existential MSO and its Relation to ETH}},
booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
pages = {42:142:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770163},
ISSN = {18688969},
year = {2016},
volume = {58},
editor = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6455},
URN = {urn:nbn:de:0030drops64556},
doi = {10.4230/LIPIcs.MFCS.2016.42},
annote = {Keywords: exponential time hypothesis (ETH), monadic second order logic, subexponential time complexity, serfreducibility, logic games}
}
Keywords: 

exponential time hypothesis (ETH), monadic second order logic, subexponential time complexity, serfreducibility, logic games 
Collection: 

41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) 
Issue Date: 

2016 
Date of publication: 

19.08.2016 