A complexity analysis of the SAT problem

MaRDI QIDQ5475258zbMATH OpenFDO

Authors Fengren Yu, Haiming Qiu

Publication date 16 June 2006

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• scientific article; zbMATH DE number 2157028
• The complexity of satisfiability problems
• scientific article; zbMATH DE number 4039349
• A simplified NP-complete satisfiability problem
• A Complexity Index for Satisfiability Problems

Cited in

(11)

• Some variants of SAT and their properties
• Some structural properties of SAT
• The SAT problem of signed CNF formulas
• scientific article; zbMATH DE number 5605058 (Why is no real title available?)
• SELF-SIMILARITY OF SATISFIABLE BOOLEAN EXPRESSIONS DECIPHERED IN TERMS OF GRAPH DIRECTED ITERATED FUNCTION SYSTEMS
• scientific article; zbMATH DE number 4031655 (Why is no real title available?)
• scientific article; zbMATH DE number 4039349 (Why is no real title available?)
• scientific article; zbMATH DE number 27687 (Why is no real title available?)
• scientific article; zbMATH DE number 6970794 (Why is no real title available?)
• scientific article; zbMATH DE number 2157028 (Why is no real title available?)
• The complexity of satisfiability problems

This page was built for publication: A complexity analysis of the SAT problem

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