Satisfiability Problem · Problem Statement

Lesson 1

Nikolai Chukhin · Alexander S. Kulikov

The satisfiability problem (SAT) is one of the most famous hard-to-solve problems. Since 1996, an international conference dedicated exclusively to this problem has been held annually. Since 2002, annual competitions of programs for solving this problem in practice, the so-called SAT solvers, are organized.

In 2021, the second edition of the handbook on the satisfiability problem, containing 1500 pages, was published in the series Frontiers of Artificial Intelligence and Applications.

On the back of the book there are three quotes from well-known scientists.

In 2015, a section dedicated to the satisfiability problem appeared in Knuth's “The Art of Computer Programming”. It is the longest section in the entire series.