Interview Cake
The Satisfiability Problem (SAT)
The satisfiability problem is central to research around whether P = NP. Here's how the problem works:
Say we have a set of light switches that can be toggled on or off. These switches are wired to lightbulbs in a complicated way—maybe one light only goes on if the first switch is down and the second switch is up. Another light might only go on if the first light is on and the third switch is down. A third light might go on if the second light is off and the first switch is up. And so on. We'd like to figure out if there's an arrangement of the switches that makes all the lights turn on.
In more math-y terms, say we have a set of boolean values (meaning they can be true or false). And, say we have some expression that combines those values using and, or, and not. The satisfiability problem asks if there's an assignment of values to each boolean that makes the whole expression evaluate to true.
As an example (\bar{x} \wedge y) \vee (x \wedge \bar{z}) is satisfiable, since we can set y = 1 and x = z = 0 to produce 1 overall.
We don't know of a polynomial time algorithm to solve SAT expressions, so SAT may or may not be in P. However, SAT is in NP. If you were given a key that specified which variables were True and which were False, then you could quickly evaluate the expression with those values and see if the result was 0 or 1.
Interview coming up?
Get the free 7-day email crash course. You'll learn how to think algorithmically, so you can break down tricky coding interview questions.
No prior computer science training necessary—we'll get you up to speed quickly, skipping all the overly academic stuff.
No spam. One-click unsubscribe whenever.
You're in! Head over to your email inbox right now to read day one!
