Exponential complexity of satisfiability testing for linear-size Boolean formulas

DOI10.1007/978-3-642-38233-8_10MaRDI QIDQ4924642zbMATH OpenOpenAlexFDO

Authors E. Ya. Dantsin, Alexander Wolpert

Publication date 7 June 2013

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-38233-8_10

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the complexity of k-SAT
• On the limits of sparsification
• A satisfiability algorithm and average-case hardness for formulas over the full binary basis
• On the complexity of circuit satisfiability
• On Linear CNF Formulas

Cited in

(6)

• Satisfiability testing for Boolean formulas using -trees
• On the limits of sparsification
• Satisfiability algorithms and lower bounds for Boolean formulas over finite bases
• A satisfiability algorithm and average-case hardness for formulas over the full binary basis
• Complexity Results for Linear XSAT-Problems
• Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis

This page was built for publication: Exponential complexity of satisfiability testing for linear-size Boolean formulas

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