On existential MSO and its relation to ETH

DOI10.1145/3417759MaRDI QIDQ5862284zbMATH OpenOpenAlexWikidataFDO

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

Publication date 7 March 2022

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2016/6455/

zbMATH Keywords

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

Mathematics Subject Classification ID

Higher-order logic (03B16) Logic in computer science (03B70) 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 Q5862284)