NP-Completeness — Brief ☧
Deep version → | Lab → | Flashcards →
Q: Joshua must divide the Promised Land among 12 tribes. Each tribe
has requirements: Judah wants the hill country, Dan wants the coast,
Naphtali wants the north. Some requirements overlap — two tribes may
want the same territory. Can Joshua find a division that makes everyone
satisfied?
A: Let us start with something simpler. Suppose there are only 3
tribes and 3 regions. You could try every way to assign regions to
tribes: Judah gets region A, Dan gets region B, Naphtali gets region
C. Then swap: Judah gets B, Dan gets A, Naphtali gets C. And so on.
With 3 tribes and 3 regions, there are only 27 combinations — you can
check them all quickly.
Q: That sounds manageable. Why would it ever be hard?
A: Because the number of possibilities explodes as the problem
grows. With 12 tribes and 50 regions, there are 12^50 possible
assignments — a number so large that even the fastest computer could
not try them all before the sun burns out. Each extra tribe or region
multiplies the possibilities. This is
exponential growth: O(2^N) or
worse.
Q: So is Joshua's problem hopeless?
A: Not exactly. Here is the key insight: even though finding a
good division might take an enormous amount of time, checking whether
a proposed division works is easy. If someone hands Joshua a map and
says "try this," he just walks through each tribe's requirements and
verifies them — that's linear
or polynomial time. The problem is finding the answer, not verifying
it.
Q: Is there a name for this kind of problem — hard to solve, easy
to verify?
A: Yes. Computer scientists organize problems into classes:
- P — problems we can both solve and verify in polynomial time (like sorting 42 names, or finding the shortest path in a graph).
- NP — problems we can verify in polynomial time but may not be able to solve quickly (like Joshua's land division, or Sudoku).
- NP-Complete — the hardest problems in NP. They have a remarkable property: if you discover a fast solution for any one of them, that solution can be transformed into a fast solution for all of them. They are all equally hard.
- NP-Hard — at least as hard as NP-Complete, but the answer might not even be verifiable quickly (like finding the truly optimal schedule).
Q: Can you give me a concrete NP-Complete example?
A: 3-SAT: you have a boolean
formula — a set of true/false variables combined with AND, OR, and
NOT. The question is: can you set the variables to make the whole
formula true? It looks simple, but with hundreds of variables, the
combinations are astronomical. Yet if someone gives you a proposed
assignment of true/false values, you can plug them in and check the
formula in linear time.
Graph coloring is another: given a
graph, can you color each node with
one of K colors so that no two connected nodes share a color? Easy to
check, brutally hard to solve.
Q: Does P = NP? Could all these "hard to solve" problems actually
have fast solutions we just haven't found yet?
A: Almost certainly not — but nobody has proved it. This is the
most famous open question in computer science, with a $1,000,000 Clay
Millennium Prize awaiting whoever resolves it.
Q: How does this connect to our FPGA?
A: miniKanren search is essentially NP-hard — it searches over
constraint assignments. Our FPGA cannot change the fundamental
difficulty: for the worst-case inputs, the search space is still
exponential. But it can explore that space much faster. Each
constraint intersection is a bitmask
AND — O(1) instead of O(N).
And 8 parallel lanes multiply throughput. We don't shrink the haystack,
but we search it thousands of times faster.
The Landscape
| Class | Can Solve Fast? | Can Verify Fast? | Example |
|---|---|---|---|
| P | Yes | Yes | Sorting, shortest path |
| NP | Unknown | Yes | Sudoku, SAT |
| NP-Complete | Unknown (probably not) | Yes | 3-SAT, graph coloring |
| NP-Hard | Unknown | Not necessarily | Halting problem, optimal scheduling |
Understanding this landscape is important because it sets realistic expectations for what hardware can and cannot do. Problems in P are "easy" in the theoretical sense — there exist algorithms that scale polynomially. Problems that are NP-Complete are "hard" — the best known algorithms take exponential time in the worst case. And NP-Hard problems are at least as hard as NP-Complete, with some (like the halting problem) being outright unsolvable.
The million-dollar question: Does P = NP? Almost certainly not.
But no one has proved it. ($1,000,000 Clay Prize awaits.)
Our FPGA cannot solve NP-complete problems in polynomial time. But it can explore the search space much faster than software — bitmask AND prunes impossible branches in O(1), and 8 parallel lanes multiply throughput. Think of it this way: the FPGA does not make the haystack smaller, but it searches through it thousands of times faster. For many practical problems (Sudoku, N-Queens, medical knowledge base queries), this speedup is the difference between "takes hours" and "takes seconds."
Learn more in the deep version
Bitmasks Sorting
Soli Deo Gloria