Computationally hard problems: 3-SAT and its polynomial solvability

MaRDI QIDQ2888335zbMATH OpenFDO

Authors Narendra S. Chaudhari

Publication date 30 May 2012

Published in The Journal of the Indian Academy of Mathematics (Search for Journal in Brave)

zbMATH Keywords

3-SAT problemliterallogical consequents

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Computational complexity of some restricted instances of 3-SAT
• Polynomially solvable satisfiability problems
• A preliminary investigation of satisfiability problems not harder than 1-in-3-SAT
• Hard random 3-SAT problems and the Davis-Putnam procedure
• A numerical approach to 3-SAT
• On problems as hard as CNF-SAT
• scientific article; zbMATH DE number 515744
• On solving hard problems by polynomial-size circuits
• A perspective on certain polynomial-time solvable classes of satisfiability
• An efficient algorithm for the 3-satisfiability problem

Cited in

(5)

• A polynomial-time reduction from the 3SAT problem to the generalized string puzzle problem
• On a simple hard variant of \textsc{Not-All-Equal} 3-\textsc{Sat}
• On the Complexity of Hmelevskii’s Theorem and Satisfiability of Three Unknown Equations
• Hard satisfiable 3-SAT instances via autocorrelation
• Conditional hardness for satisfiable 3-CSPs

This page was built for publication: Computationally hard problems: 3-SAT and its polynomial solvability

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