Maximum satisfiability and subexponential time

MaRDI QIDQ3001095zbMATH OpenFDO

Authors E. Ya. Dantsin

Publication date 31 May 2011

zbMATH Keywords

3-CNF3-SATBoolean satisfiability problemsubexponential complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the complexity of k-SAT
• Parameterized and subexponential-time complexity of satisfiability problems and applications
• A new upper bound for \(( n , 3)\)-MAX-SAT
• On the subexponential-time complexity of CSP
• Sparsification and subexponential approximation

Cited in

(3)

• Satisfiability certificates verifiable in subexponential time
• On moderately exponential time for SAT
• On the subexponential-time complexity of CSP

This page was built for publication: Maximum satisfiability and subexponential time

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