On existential MSO and its relation to ETH

DOI10.1145/3417759zbMATH Open1495.68088OpenAlexW3044065395WikidataQ130878666 ScholiaQ130878666MaRDI QIDQ5862284FDOQ5862284

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/

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

zbMATH Keywords

monadic second-order logiclogic gamessubexponential time complexityexponential time hypothesis (ETH)serf-reducibility

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Higher-order logic (03B16) Logic in computer science (03B70)

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)