Algorithms For Dummies

Solving satisfiability of Boolean circuits

As a practical view of how a local search works, this example delves into circuit 

satisfiability, a classical NP-complete problem. It uses a randomization and Monte 

Carlo algorithm approach. As seen in Chapter 17, a Monte Carlo algorithm relies on 

random choices during its optimization process and isn’t guaranteed to succeed in 

its task, although it has a high likelihood of completing the task successfully. The 

problem isn’t merely theoretical, though, because it tests how electronic circuits 

work, optimizing them by removing circuits that can’t transport electric signals. 

Moreover, the solving algorithm sees use in other applications: automatic labeling 

on maps and charts, discrete tomography, scheduling with constraints, data clus-

tering into groups, and other problems for which you have to make conflicting 

choices.

---

CHAPTER 18