On existential MSO and its relation to ETH

DOI10.4230/LIPICS.MFCS.2016.42MaRDI QIDQ4608603zbMATH OpenOpenAlexFDO

Authors Robert Ganian, Ronald de Haan, Stefan Szeider, Iyad Kanj

Publication date 21 March 2018

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2016/6455/pdf/LIPIcs-MFCS-2016-42.pdf/

zbMATH Keywords

exponential time hypothesis (ETH)logic gamesmonadic second-order logicserf-reducibilitysubexponential time complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On existential MSO and its relation to ETH
• Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis
• On moderately exponential time for SAT
• Parameterized and subexponential-time complexity of satisfiability problems and applications
• The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems

Cited in

(1)

• On existential MSO and its relation to ETH

This page was built for publication: On existential MSO and its relation to ETH

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608603)