On Existential MSO and its Relation to ETH
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F16%3A00093950" target="_blank" >RIV/00216224:14330/16:00093950 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.4230/LIPIcs.MFCS.2016.42" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.MFCS.2016.42</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.MFCS.2016.42" target="_blank" >10.4230/LIPIcs.MFCS.2016.42</a>
Alternative languages
Result language
angličtina
Original language name
On Existential MSO and its Relation to ETH
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26
ISBN
9783959770163
ISSN
1868-8969
e-ISSN
—
Number of pages
14
Pages from-to
42,1-14
Publisher name
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Place of publication
Germany
Event location
Poland
Event date
Jan 1, 2016
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—