Page "Boolean satisfiability problem" Paragraph 6

The Cook – Levin theorem states that the Boolean satisfiability problem is NP-complete, and in fact, this was the first decision problem proved to be NP-complete.

However, beyond this theoretical significance, efficient and scalable algorithms for SAT that were developed over the last decade have contributed to dramatic advances in our ability to automatically solve problem instances involving tens of thousands of variables and millions of constraints.

Examples of such problems in electronic design automation ( EDA ) include formal equivalence checking, model checking, formal verification of pipelined microprocessors, automatic test pattern generation, routing of FPGAs, and so on.

A SAT-solving engine is now considered to be an essential component in the EDA toolbox.