JOVANA
Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

When Problems Are Hard: P, NP & Intractability

Some problems we can solve fast; some we can only *check* fast; and for a famous family, nobody knows if a fast solution exists at all. This guide explains P, NP, and NP-completeness honestly — including the part that is still an open question — and tells you what to actually do when you hit a hard problem.

Solving fast vs checking fast

Everything you have built so far runs in polynomial time — a cost like n, n log n, or n^2, expressed in [[big-o-notation|Big-O notation]]. The class of problems with such an algorithm is called P (for polynomial). These are the problems we consider "efficiently solvable": as the input grows, the work grows at a manageable, predictable rate.

Now a subtler class. NP is the set of problems where, *if someone hands you a candidate answer, you can check it quickly* (in polynomial time) — even if finding that answer might be hard. Think of a giant jigsaw: assembling it could take ages, but verifying a finished puzzle is correct takes one glance. Every problem in P is also in NP (if you can solve it fast, you can certainly check it fast), so P sits inside NP.

        +-------------------------- NP --------------------------+
        |   (answers are checkable fast)                          |
        |                                                         |
        |    +--------- P ---------+        +-- NP-complete --+    |
        |    | solvable fast       |        | hardest in NP   |    |
        |    | (sort, search, MST) |        | (SAT, TSP, ...) |    |
        |    +---------------------+        +-----------------+    |
        +---------------------------------------------------------+

  Open question:  is P = NP ?  i.e. does the P box secretly fill all of NP?
P sits inside NP. Whether they are actually equal — whether the P box quietly fills the whole NP box — is unknown.

NP-complete and the open question

Inside NP lives a special family: the [[np-completeness|NP-complete]] problems. These are the *hardest* problems in NP, in a precise sense — and they are all tied together. We know how to reduce any one of them into any other: rewrite an instance of problem A as an instance of problem B in polynomial time, so that solving B solves A. Because of this web of reductions, if anyone ever found a fast (polynomial-time) algorithm for *one single* NP-complete problem, that algorithm would instantly give fast solutions for *all* of them.

  1. SAT (Boolean satisfiability): given a logical formula, is there an assignment of true/false to its variables that makes the whole thing true? Checking a proposed assignment is instant; finding one is the hard part. SAT was the first problem proven NP-complete.
  2. TSP (the decision form of the Travelling Salesman Problem): given cities and a budget, is there a route visiting all of them within that budget? Verifying a route's length is easy; searching among the astronomically many routes is not.
  3. Graph coloring, subset-sum, the knapsack decision problem, and hundreds more all sit in this same club, linked by reductions. Solve one fast, and you solve them all.

What to do with a hard problem

Suppose you've identified that your problem is NP-hard (at least as hard as the NP-complete ones). That is not a dead end — it is a redirection. It tells you to stop hunting for a perfect, fast, exact algorithm and instead spend your effort somewhere it can pay off. You have several honest options.

  1. Approximation: accept an answer that is provably close to optimal but found quickly. For many NP-hard problems there are algorithms that guarantee, say, "within 5% of the best possible" in polynomial time.
  2. Heuristics: use clever rules of thumb (greedy choices, local search) that work well on typical inputs even without a guarantee. They power real route planners and schedulers.
  3. Exponential-but-pruned exact search: when the instance is small, an exact algorithm that explores the search space while cutting off hopeless branches (branch and bound, the pruning you saw in backtracking) can finish in practice, even if the worst case is exponential.
  4. Restrict the problem: sometimes the special case you actually face (a tree instead of a general graph, small integer weights) has a fast algorithm even though the general problem does not.