Algorithmic Foundations

Complexity Classes

P is the class of problems solvable in polynomial time; NP is the class whose solutions can be verified in polynomial time. Whether P = NP is the central open question of computer science — and in practice, treating a problem as NP-hard changes how you approach it.

P: solvable in polynomial time. NP: a proposed solution can be checked in polynomial time (not necessarily found quickly)
Every problem in P is in NP — if you can solve it quickly, you can trivially verify a solution quickly
NP-complete problems are the hardest problems in NP: every NP problem reduces to them in polynomial time
No polynomial-time algorithm is known for any NP-complete problem, and finding one would prove P = NP
Recognizing a problem is NP-hard is actionable: stop searching for an exact polynomial algorithm, switch to heuristics, approximation, or restricting the input

The asymmetry between P and NP is the whole story: for a problem like the Traveling Salesman Problem, nobody knows how to find a shortest route faster than roughly trying all permutations, but given a candidate route, checking that it is under some length budget and visits every city once is trivially fast — sum the edge weights, compare. NP is exactly this class of "easy to check, seemingly hard to solve."

Where familiar problems sit
Class	Meaning	Examples
P	Solvable in polynomial time	Sorting, shortest paths (Shortest Paths), matching
NP	Solution verifiable in polynomial time	Everything in P, plus SAT, TSP decision version, subset sum
NP-complete	The hardest problems in NP; all of NP reduces to them	3-SAT, vertex cover, knapsack (decision version)
NP-hard	At least as hard as NP-complete, not necessarily in NP itself	The optimization (not decision) version of TSP

Easy to verify, believed hard to solve — subset sum

// Given a candidate subset, VERIFYING it sums to the target is O(n): trivially in NP.
static boolean verifySubset(int[] chosen, int target) {
    int sum = 0;
    for (int x : chosen) sum += x;
    return sum == target;
}

// SOLVING (finding such a subset) has no known polynomial algorithm in general —
// the brute-force search below is O(2^n), one bit per element for "in / out".
static boolean subsetSumExists(int[] a, int target) {
    int n = a.length;
    for (int mask = 0; mask < (1 << n); mask++) {
        int sum = 0;
        for (int i = 0; i < n; i++) if ((mask & (1 << i)) != 0) sum += a[i];
        if (sum == target) return true;
    }
    return false;
}