Overview

The Satisfiability (Sat) Problem: A member of the NP Complete family (the most challenging of the non-deterministic polynomial time problems, can be compared to an analogy of locks and keys. Imagine a hallway of 4 doors, each with one lock.

each lock on each door can be opened by two different keys, (represented by the letters on each door- so the first lock can be opened by either the "G" (first green key) or the "B"(first blue key).) As long as you have at least one of the keys you can open the door. A janitor then, with three sets of keys blue ,(B,b), green ,(G,g), red ,(R,r)wants to find the combination of one blue key, one green key, and one red key that will open all four of the doors. The graphic below illustrates 3 of the janitor's possible 8 key combinations, and out of this set, only the first key ring can open all four doors. This key ring is said to "satisfy" the door problem.

Testing different keys