Complexity Classes: P and NP — Junior Level¶

Audience: You know Big-O and basic algorithms (sorting, BFS, hash tables) but have never met "P," "NP," or "complexity class." Read time: ~35 minutes. Focus: "What do P and NP actually mean?" and "Why is finding an answer sometimes hard when checking it is easy?"

Table of Contents¶

1. Introduction
2. Prerequisites
3. Glossary
4. The Big Idea: Solving vs. Checking
5. Decision Problems: Everything Is a Yes/No Question
6. The Class P: Problems We Can Solve Fast
7. The Class NP: Problems We Can Check Fast
8. A Verifier, Concretely: Subset-Sum in Code
9. Why P ⊆ NP
10. The Containment Picture: P ⊆ NP ⊆ EXP
11. A Table of Problems by Class
12. NP-Completeness in One Paragraph
13. The Million-Dollar Question: Does P = NP?
14. Real-World Analogies
15. Why This Matters in Practice
16. Common Misconceptions
17. Common Mistakes
18. Cheat Sheet
19. Summary
20. Further Reading

Introduction¶

You already know how to compare algorithms with Big-O. Binary search is O(log n), merge sort is O(n log n), the naive "compare every pair" approach is O(n²). That lets you rank algorithms against each other.

Complexity classes ask a bigger, scarier question. Not "how fast is this algorithm?" but "how fast can any algorithm possibly be for this problem?" That shift — from one solution to the entire universe of possible solutions — is what complexity theory is about. It is the difference between asking "how good is my chess opening?" and asking "is chess even winnable?"

Two classes sit at the center of this story: P and NP. Stripped of all jargon:

• P is the set of problems a computer can solve quickly.
• NP is the set of problems where, if someone hands you an answer, you can check it quickly.

The headline mystery — one of the deepest open questions in all of mathematics and computer science — is whether these two sets are actually the same. If every problem whose answer is easy to check is also easy to solve, then P = NP and the world changes overnight. Nobody knows. There is a literal $1,000,000 prize waiting for whoever settles it.

This file teaches the intuition: decision problems, what P really means, the "verifier" view of NP that makes everything click, a small piece of working code so "verify in polynomial time" stops being abstract, and why a 50-year-old open question quietly underpins the encryption protecting your bank account.

Prerequisites¶

• Required: Big-O basics — what O(n), O(n²), O(2ⁿ) mean and how they grow. See Time vs Space Complexity.
• Required: Familiarity with a few standard algorithms (sorting, BFS/DFS, shortest paths). See Common Runtimes.
• Helpful: The intuition that O(n²) is "polynomial" and O(2ⁿ) is "exponential," and that exponential blows up catastrophically.
• Helpful: Comfort reading short snippets in Go, Java, or Python — we use one of each.

No prior exposure to Turing machines, formal languages, or proofs is assumed. We build everything from examples.

Glossary¶

The Big Idea: Solving vs. Checking¶

Before any formal definitions, sit with this one observation, because it is the soul of the entire topic:

For some problems, finding the answer is enormously hard, but checking a proposed answer is trivially easy.

A perfect everyday example is a jigsaw puzzle. Assembling a 5,000-piece puzzle from scratch can take days. But if I show you a completed puzzle and ask "is this assembled correctly?", you can verify it in a glance — every piece interlocks, the picture is coherent. Solving is hard; checking is easy.

Another: a hard Sudoku. Filling in a brutal Sudoku grid might take you an hour of careful logic. But if I hand you a filled-in grid and ask "is this a valid solution?", you just scan every row, column, and box for duplicates — a couple of minutes, mechanical, no cleverness required. Solving is hard; checking is easy.

This asymmetry is not a quirk of puzzles. It shows up in routing, scheduling, circuit design, protein folding, and — crucially — cryptography. The entire P-versus-NP question is, at heart, asking:

Is "checking is easy" secretly the same as "solving is easy"? Or is there a real, permanent gap between the two?

Hold onto the jigsaw and the Sudoku. We will return to them once the formal terms are in place, and they will make the definitions feel obvious instead of intimidating.

Decision Problems: Everything Is a Yes/No Question¶

Complexity theory studies decision problems — problems whose answer is a single bit: yes or no. That sounds limiting. Most real problems aren't yes/no — "find the shortest route," "schedule these tasks," "pick the best subset." So why restrict to yes/no?

Two reasons.

Reason 1: It makes the math clean. A yes/no answer is the simplest possible output. By forcing every problem into this mold, we get a uniform way to compare problems of wildly different shapes. We can put "is this graph connected?" and "is there a route under 100 km?" on the same footing.

Reason 2: Decision versions capture the difficulty of the full problem. Almost any optimization problem has a decision twin that is essentially just as hard:

If you could answer the decision twin quickly for every value of k, you could pin down the optimal value quickly too (just try increasing k, or binary-search on it). So studying the yes/no version loses almost nothing — and gains a clean theory.

Problems as "languages"¶

You'll sometimes hear a decision problem called a language. Don't let the word scare you. It just means: the set of all inputs whose answer is yes. For the problem "is this number prime?", the "language" is simply the set {2, 3, 5, 7, 11, 13, ...}. Asking "does the algorithm decide this language?" is just a formal way of asking "does the algorithm correctly answer yes/no on every input?" We'll mostly stick with plain English — "the problem" — and you can mentally swap in "language" whenever you read it elsewhere.

The Class P: Problems We Can Solve Fast¶

P stands for Polynomial time. A decision problem is in P if there exists an algorithm that solves it — outputs the correct yes/no — in time bounded by O(nᵏ) for some fixed constant k, where n is the input size.

In plain terms: P is the set of problems you can solve efficiently with an ordinary algorithm. O(n), O(n log n), O(n²), O(n³) all count. They are all "polynomial." What does not count is exponential time like O(2ⁿ) or O(n!).

Why "polynomial" is the dividing line¶

Why draw the line exactly at polynomial? Because of how the numbers actually behave. Watch what happens as input size grows:

A polynomial algorithm at n = 100 does ten thousand operations — instant. An exponential one does 10³⁰ operations — it would not finish before the sun burns out. Polynomial growth stays in the realm of the possible; exponential growth crosses into the physically impossible almost immediately. That cliff is why complexity theorists treat "polynomial" as the practical definition of tractable (solvable in practice) and "exponential" as the warning sign of intractable.

It's a rough line — an O(n¹⁰⁰) algorithm is technically "in P" but useless in practice, and constants matter. But as a first-order map of "what's realistically solvable," polynomial-vs-exponential is remarkably sharp.

Examples of problems in P¶

These are problems you very likely already know how to solve efficiently:

• Sorting — O(n log n) with merge sort or heapsort.
• Searching a sorted array — O(log n) with binary search.
• Shortest path in a graph — BFS for unweighted (O(V + E)), Dijkstra for weighted (O(E log V)).
• String matching — finding a pattern in text, O(n + m) with KMP.
• Primality testing — "is n prime?" The AKS algorithm (2002) does this in polynomial time. (This one was a genuine surprise; for decades nobody knew if primality was in P, though they suspected it.)
• 2-SAT — a restricted form of the satisfiability problem, solvable in linear time.
• Maximum matching in a graph — pairing up nodes optimally, polynomial via Edmonds' algorithm.

If a problem is in P, you can stop worrying. There is a fast, exact algorithm. The interesting drama is all about the problems that aren't (yet) known to be in P.

The Class NP: Problems We Can Check Fast¶

Here is the class that confuses everyone — usually because of its name, which we'll demolish in a moment. Let's define it the intuitive way first.

A decision problem is in NP if, whenever the answer is yes, there exists a short "proof" of that yes — called a certificate or witness — that you can verify in polynomial time.

Read that again with the jigsaw puzzle in mind:

• The certificate is the completed puzzle (the proposed answer).
• The verifier is you, glancing at it and confirming every piece fits.
• "In polynomial time" means that glance is fast — proportional to the number of pieces, not exponential.

So NP is the class of problems where a "yes" answer is easy to check once someone gives you the answer — even if finding that answer might be horrendously hard.

The verifier definition, precisely¶

A problem is in NP if there's a polynomial-time algorithm verify(input, certificate) such that:

• If the true answer for input is yes, then there exists some certificate that makes verify return yes.
• If the true answer is no, then no certificate can fool verify into returning yes.

The certificate must be polynomial in size (not gigantic), and verify must run in polynomial time. That's the whole definition. Notice it never asks you to find the certificate — only to check one you're given. That's the magic. Finding can be exponentially hard; the definition only cares that checking is cheap.

Examples of problems in NP¶

• SAT (Boolean satisfiability): "Is there an assignment of true/false to these variables that makes this logical formula true?" Certificate: the assignment itself. Verifier: plug the values in, evaluate the formula — fast.
• Subset-Sum: "Does some subset of these numbers add up to exactly the target?" Certificate: the actual subset. Verifier: add it up, compare to target — O(n).
• Hamiltonian Cycle: "Is there a route visiting every city exactly once and returning to start?" Certificate: the proposed route (an ordering of cities). Verifier: check it visits each city once and each step is a real road — fast.
• Graph 3-Coloring: "Can this graph's nodes be colored with 3 colors so no edge connects two same-colored nodes?" Certificate: the coloring. Verifier: check every edge's endpoints differ — fast.
• Clique: "Does this graph contain a group of k nodes all mutually connected?" Certificate: the k nodes. Verifier: check all pairs among them are edges — fast.
• Traveling Salesman (decision version): "Is there a tour of all cities with total length under k?" Certificate: the tour. Verifier: sum the distances, compare to k — fast.

In every case: finding the certificate looks brutally hard (we know no polynomial algorithm), but verifying a given one is trivially polynomial. That pattern — hard to find, easy to check — is NP.

The other definition: Nondeterministic Polynomial time¶

NP officially stands for Nondeterministic Polynomial time, and that's where the equivalent (more formal) definition comes from. Imagine a magical computer that, whenever it faces a choice, can guess the right branch — explore all possibilities at once. Such a "nondeterministic" machine could guess the correct certificate and then verify it in polynomial time. A problem is in NP if this magical machine could solve it in polynomial time.

The two definitions — "verify a given certificate fast" and "a guessing machine solves it fast" — are provably equivalent. The verifier view is far easier to reason about, so it's the one we use. But now you know what the letters stand for, which leads straight to the single most important warning in this whole file.

A Verifier, Concretely: Subset-Sum in Code¶

"Verify in polynomial time" stays abstract until you write one. So let's write a verifier for Subset-Sum.

The problem: Given a list of integers and a target, is there a subset that sums to exactly the target?

Finding such a subset by brute force means trying all 2ⁿ subsets — exponential. But verifying a proposed subset is dead simple: add it up, confirm it equals the target, and confirm every element really came from the original list. That's O(n). Here it is in three languages.

Go¶

package main

import "fmt"

// verifySubsetSum checks a CERTIFICATE (the proposed subset) in polynomial time.
// It does NOT solve the problem — it only verifies a given answer.
func verifySubsetSum(nums []int, target int, subset []int) bool {
    // 1. Count how many of each value the original list offers.
    available := make(map[int]int)
    for _, v := range nums {
        available[v]++
    }

    // 2. Every element of the certificate must be drawn from the list
    //    (and not reused more times than it appears).
    for _, v := range subset {
        if available[v] == 0 {
            return false // claimed an element that isn't available
        }
        available[v]--
    }

    // 3. The subset must sum to exactly the target.
    sum := 0
    for _, v := range subset {
        sum += v
    }
    return sum == target
}

func main() {
    nums := []int{3, 34, 4, 12, 5, 2}
    target := 9

    // A correct certificate: 4 + 5 = 9.
    fmt.Println(verifySubsetSum(nums, target, []int{4, 5})) // true

    // A wrong certificate: 3 + 5 = 8, not 9.
    fmt.Println(verifySubsetSum(nums, target, []int{3, 5})) // false

    // A cheating certificate: 9 isn't even in the list.
    fmt.Println(verifySubsetSum(nums, target, []int{9})) // false
}

Java¶

import java.util.HashMap;
import java.util.Map;

public class SubsetSumVerifier {

    // Verifies a CERTIFICATE in polynomial time. Does not solve anything.
    static boolean verify(int[] nums, int target, int[] subset) {
        // 1. Tally what the original list makes available.
        Map<Integer, Integer> available = new HashMap<>();
        for (int v : nums) {
            available.merge(v, 1, Integer::sum);
        }

        // 2. Each certificate element must come from the list.
        for (int v : subset) {
            int count = available.getOrDefault(v, 0);
            if (count == 0) return false;
            available.put(v, count - 1);
        }

        // 3. Must sum to exactly the target.
        int sum = 0;
        for (int v : subset) sum += v;
        return sum == target;
    }

    public static void main(String[] args) {
        int[] nums = {3, 34, 4, 12, 5, 2};
        int target = 9;

        System.out.println(verify(nums, target, new int[]{4, 5})); // true
        System.out.println(verify(nums, target, new int[]{3, 5})); // false
        System.out.println(verify(nums, target, new int[]{9}));    // false
    }
}

Python¶

from collections import Counter

def verify_subset_sum(nums, target, subset):
    """Verify a CERTIFICATE (proposed subset) in polynomial time.
    This only CHECKS an answer; it does not FIND one."""
    available = Counter(nums)          # what the original list offers

    for v in subset:                   # every element must come from the list
        if available[v] == 0:
            return False
        available[v] -= 1

    return sum(subset) == target       # must total exactly the target


if __name__ == "__main__":
    nums, target = [3, 34, 4, 12, 5, 2], 9

    print(verify_subset_sum(nums, target, [4, 5]))  # True  (4 + 5 = 9)
    print(verify_subset_sum(nums, target, [3, 5]))  # False (3 + 5 = 8)
    print(verify_subset_sum(nums, target, [9]))     # False (9 not in list)

What this code proves about NP¶

Look at the running time of verify: one pass to tally, one pass to check membership, one pass to sum. That's O(n) — comfortably polynomial. The certificate (the subset) is at most as long as the input — polynomial in size. Both conditions of the NP definition are satisfied, so Subset-Sum is in NP.

Now notice what the code doesn't do. It never searches for the subset. It is handed one. The exponential difficulty of Subset-Sum lives entirely in finding the certificate — which we deliberately skipped. That gap, between the cheap verifier you just read and the expensive search you didn't write, is the precise reason Subset-Sum sits in NP but isn't (as far as anyone knows) in P.

Why P ⊆ NP¶

A clean, important fact you can prove to yourself in one sentence:

Every problem in P is also in NP. In symbols: P ⊆ NP ("P is a subset of NP").

Why? If you can solve a problem in polynomial time, then you can verify it in polynomial time too — just ignore whatever certificate you're given and solve the problem from scratch with your fast algorithm. If your solver says yes, return yes; if it says no, return no. You don't even need the hint. A fast solver is automatically a fast verifier.

So solving-fast is at least as strong as checking-fast, which means everything in P lands inside NP. P sits inside NP, like a smaller circle inside a bigger one.

The trillion-dollar question — literally the rest of this file — is whether that bigger circle has anything extra in it. Are there problems in NP (easy to check) that are genuinely not in P (hard to solve)? Or is NP just P wearing a disguise?

The Containment Picture: P ⊆ NP ⊆ EXP¶

Zoom out and you get a tidy nesting of three classes:

        ┌─────────────────────────────────────┐
        │  EXP  (solvable in exponential time) │
        │   ┌─────────────────────────────┐    │
        │   │  NP  (verifiable fast)       │    │
        │   │    ┌───────────────────┐     │    │
        │   │    │   P               │     │    │
        │   │    │ (solvable fast):  │     │    │
        │   │    │ sorting, BFS,     │     │    │
        │   │    │ shortest path,    │     │    │
        │   │    │ 2-SAT, matching   │     │    │
        │   │    └───────────────────┘     │    │
        │   │  SAT, TSP, clique,           │    │
        │   │  subset-sum, 3-coloring      │    │
        │   └─────────────────────────────┘    │
        │  chess (n×n), generalized games...   │
        └─────────────────────────────────────┘

• P ⊆ NP: anything you can solve fast, you can check fast (we just proved this).
• NP ⊆ EXP: anything you can verify fast, you can solve in exponential time — just brute-force every possible certificate and run the polynomial verifier on each. There are at most exponentially many certificates, so the whole search is exponential. Slow, but it always terminates with the right answer.

So we know P ⊆ NP ⊆ EXP. What nobody knows is whether the first containment is strict. The picture above draws NP as strictly bigger than P, but that's just the way most researchers bet it goes — it has never been proven. The two inner circles might secretly be the exact same circle.

A Table of Problems by Class¶

A reference map of where common problems sit. Read "in P" as we have a fast algorithm, and "NP-complete" as in NP, and among the hardest there — no fast algorithm known (more on that next).

Notice the pattern in the bottom half: every NP-complete problem shares the "easy to check, hard to find" signature. They feel different on the surface — logic, arithmetic, routing, coloring — but underneath, they are all the same difficulty. That surprising fact is what NP-completeness is about.

NP-Completeness in One Paragraph¶

Within NP, some problems are the hardest of all — they're called NP-complete. A problem is NP-complete if (1) it's in NP, and (2) every other problem in NP can be efficiently transformed ("reduced") into it. The astonishing consequence: the NP-complete problems are all secretly equivalent. If anyone ever finds a polynomial-time algorithm for one NP-complete problem — say SAT — that algorithm could be mechanically adapted to solve every problem in NP quickly, instantly proving P = NP. Conversely, if even one NP-complete problem is truly intractable, then all of them are, and P ≠ NP. SAT, subset-sum, the Hamiltonian cycle, 3-coloring, clique, and decision-TSP are all NP-complete — which is why none of them has a fast algorithm: a fast algorithm for any one would crack them all. That's all you need for now. The full machinery — what a "reduction" is, how to prove a problem NP-complete, the Cook–Levin theorem — lives in Reductions & NP-Completeness, and what to do when you're stuck with one of these is covered in Approximation & Hardness.

One more term: NP-hard means "at least as hard as every problem in NP" — but without the requirement of being in NP itself. So NP-complete = NP-hard AND in NP. Some NP-hard problems (like the optimization version of TSP, or the halting problem) are even harder and don't fit inside NP at all. Junior takeaway: NP-complete = the hardest problems that are still in NP.

The Million-Dollar Question: Does P = NP?¶

We've arrived at the headline. We know P ⊆ NP. The open question is whether they're equal:

P = NP? — Is every problem whose answer is easy to check also easy to solve?

This is one of the seven Clay Millennium Prize Problems, each carrying a $1,000,000 reward. It has resisted every assault since it was formalized in 1971. Nobody has proven P = NP. Nobody has proven P ≠ NP. It is wide open.

What it would mean if P = NP¶

Suppose someone proves P = NP and hands us a practical polynomial algorithm for an NP-complete problem. The consequences are staggering:

• Optimization becomes trivial. Scheduling, routing, packing, chip design, protein folding — thousands of currently-intractable problems would all become efficiently solvable. Logistics and drug discovery would be revolutionized.
• Mathematics changes character. Finding a proof of a theorem is, in a sense, an NP problem (checking a proof is easy; finding it is hard). P = NP would mean machines could find proofs nearly as easily as they check them.
• Cryptography collapses. This is the scary one. The encryption guarding your passwords, bank transfers, and messages relies on certain problems being hard to solve but easy to check. P = NP would mean those problems are actually easy to solve — and most modern cryptography would crumble.

What most experts believe¶

The overwhelming consensus is P ≠ NP — that the easy-to-check / hard-to-solve gap is real and permanent. The intuition: we've thrown 50+ years of brilliance at NP-complete problems and never found a fast algorithm for even one, despite enormous incentive. It feels like solving is genuinely harder than checking. But feelings aren't proofs. Until someone produces a real proof, P = NP remains a live (if unlikely) possibility, and the million dollars stays unclaimed.

Why the answer being "hard" is, oddly, good news¶

Here's the twist that surprises newcomers: a great deal of modern technology quietly depends on P ≠ NP being true. If hard problems weren't hard, secure communication as we know it wouldn't exist. So the failure to find fast algorithms isn't just an unsolved puzzle — it's the load-bearing assumption underneath the security of the internet.

Real-World Analogies¶

The jigsaw puzzle (NP in one image). Assembling a 5,000-piece puzzle: hours of hard work (solving). Confirming a completed puzzle is correct: one glance (verifying). Hard to find, easy to check — that's NP.

The locked treasure chest. Finding the key by trying every combination is exponential. But once you have the right key, checking that it opens the chest takes one turn. The key is the certificate; turning it is the verifier.

The hard Sudoku. Solving a fiendish grid: an hour of logic. Checking a filled grid for duplicate digits in any row, column, or box: a couple of mechanical minutes. Solving hard, checking easy.

The maze. Finding the path out of a giant maze can require exploring countless dead ends. But if I draw a path on the map and claim it's a way out, you can trace it in seconds to confirm. Finding the route is the search; tracing it is the verifier.

The detective. Cracking a case from scratch is hard (NP-style search). Reading a written confession and confirming it fits all the evidence is easy (polynomial verification). P = NP would be like saying every solvable case can be cracked as fast as a confession can be checked — which is exactly why most people doubt it.

Why This Matters in Practice¶

You're a working engineer, not a theorist. Why should you care about P and NP?

1. It tells you when to stop searching for a perfect algorithm. Suppose your task reduces to graph 3-coloring or subset-sum. If you recognize it as NP-complete, you know not to waste a week hunting for a fast exact algorithm — none is known, and you'd be racing the entire field of computer science. That recognition is a superpower: it redirects your effort from "find the optimal algorithm" to "find a good-enough strategy."

2. It points you toward the right escape hatches. When you hit an NP-complete wall, you don't give up — you switch tactics: approximation algorithms (accept a near-optimal answer), heuristics (smart guessing that's usually good), exponential algorithms on small inputs (fine when n is tiny), or special-case algorithms (your real-world inputs may have structure that's easier than the general case). See Approximation & Hardness for the playbook.

3. It's the foundation of cryptography. Every time you see a padlock in your browser, you're trusting that certain problems are hard to solve. Understanding P vs NP is understanding why that padlock can be trusted at all.

4. It sharpens your instinct for problem difficulty. Even informally, learning to ask "is checking easier than solving here?" trains you to smell intractability early — before you've sunk days into an approach that can't scale.

Common Misconceptions¶

These trip up nearly everyone. Internalize them and you'll already understand NP better than most.

❌ "NP means 'non-polynomial' / 'not solvable in polynomial time'." This is the single most common error, and the name is to blame. NP stands for Nondeterministic Polynomial, not "non-polynomial." NP is about verifying in polynomial time. In fact every problem in P is also in NP, so NP is full of perfectly fast-to-solve problems. NP ≠ "hard."

❌ "NP problems are unsolvable." False. Every NP problem is solvable — you can always brute-force it in exponential time and get the right answer. They're not unsolvable; they're (apparently) not solvable quickly. "Unsolvable" problems (like the halting problem) are a completely different and much harsher category.

❌ "NP-hard and NP-complete are the same thing." Close but not equal. NP-complete = NP-hard and in NP. NP-hard means "at least as hard as everything in NP" — some NP-hard problems sit outside NP (they're even harder, or not even decision problems). All NP-complete problems are NP-hard; not all NP-hard problems are NP-complete.

❌ "P = NP has been proven false." No. It's unproven in both directions. Most experts believe P ≠ NP, but belief isn't proof. The question is genuinely open, and the $1,000,000 prize is unclaimed precisely because nobody has settled it either way.

❌ "If a problem is NP-complete, there's no algorithm for it at all." There is — it just isn't fast. You can solve any NP-complete problem exactly with exponential brute force, or approximately with fast heuristics. NP-complete means "no known polynomial algorithm," not "no algorithm."

❌ "Big-O and complexity classes are the same topic." Related but distinct. Big-O measures one algorithm's growth rate. A complexity class is about the problem itself — the best that any algorithm could possibly achieve. Big-O is a tool; complexity classes are a classification of problems.

Common Mistakes¶

Cheat Sheet¶

DECISION PROBLEM  → answer is yes/no. The object complexity theory studies.

P   = solvable fast        (polynomial-time algorithm exists)
NP  = checkable fast       (poly-time verifier for a poly-size certificate)
EXP = solvable in exp time (brute force always works, just slowly)

KNOWN:        P ⊆ NP ⊆ EXP
OPEN ($1M):   Is P = NP?   (most believe NO)

THE INTUITION:
  P   →  finding the answer is easy
  NP  →  CHECKING an answer is easy (finding may be hard)

CERTIFICATE  = the proposed answer (subset, route, coloring, assignment)
VERIFIER     = poly-time algorithm: verify(input, certificate) → yes/no

IN P:           sorting, BFS/Dijkstra, primality (AKS), 2-SAT, matching
NP-COMPLETE:    SAT, subset-sum, Hamiltonian cycle, 3-coloring, clique, TSP

NP-COMPLETE = in NP + every NP problem reduces to it = "hardest in NP"
NP-HARD     = at least as hard as all of NP (need NOT be in NP itself)
NP-COMPLETE = NP-HARD ∩ NP

NAME TRAP:  NP = "Nondeterministic Polynomial", NOT "non-polynomial"!

Summary¶

• Complexity theory studies decision problems (yes/no questions) and asks how hard a problem is — the best any algorithm could do — not how fast one particular algorithm runs.
• P is the class of problems solvable in polynomial time: sorting, shortest path, primality, 2-SAT, matching. These are "tractable."
• NP is the class of problems whose yes-answers can be verified in polynomial time given a short certificate. The killer intuition: finding is hard, checking is easy — the jigsaw, the Sudoku, the locked chest.
• The verifier view is the easiest way to think about NP, and you wrote one: a polynomial-time verify(input, certificate) for Subset-Sum that checks a proposed subset in O(n) without ever searching for it.
• P ⊆ NP because any fast solver is automatically a fast verifier. The full nesting is P ⊆ NP ⊆ EXP, all containments known.
• The NP-complete problems (SAT, subset-sum, Hamiltonian cycle, 3-coloring, clique, TSP) are the hardest in NP and are all secretly equivalent; NP-hard is the broader "at least as hard as NP" category.
• P =? NP is a $1,000,000 Clay Millennium Prize open question. Most believe P ≠ NP, and modern cryptography quietly depends on it being true.
• Biggest trap: NP means Nondeterministic Polynomial, not "non-polynomial." NP is about easy checking, not difficulty.

Further Reading¶

• Reductions & NP-Completeness — what a reduction is, the Cook–Levin theorem, and how to prove a problem NP-complete.
• Approximation & Hardness — the practical playbook for when you hit an NP-complete wall: approximation, heuristics, special cases.
• Time vs Space Complexity — the Big-O foundations underpinning "polynomial time."
• Common Runtimes — a gallery of growth rates, including where exponential time falls off the cliff.
• Complexity Classes: P and NP — Middle Level — the next step: formal definitions, the nondeterministic Turing machine, and a deeper look at the structure of NP.
• Introduction to Algorithms (CLRS), Chapter 34 — the standard textbook treatment of NP-completeness.
• Computers and Intractability by Garey & Johnson — the classic, surprisingly readable guide to NP-completeness and the famous catalog of NP-complete problems.