On moderately exponential time for SAT

DOI10.1007/978-3-642-14186-7_27MaRDI QIDQ4930599zbMATH OpenOpenAlexWikidataFDO

Authors E. Ya. Dantsin, Alexander Wolpert

Publication date 29 September 2010

Published in Theory and Applications of Satisfiability Testing – SAT 2010 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-14186-7_27

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis
• Maximum satisfiability and subexponential time
• Strong partial clones and the time complexity of SAT problems
• On the complexity of k-SAT
• On problems as hard as CNF-SAT

Cited in

(5)

• Fixed-parameter tractability of treewidth and pathwidth
• scientific article; zbMATH DE number 1555929 (Why is no real title available?)
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• On existential MSO and its relation to ETH
• On existential MSO and its relation to ETH

This page was built for publication: On moderately exponential time for SAT

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