P vs NP & NP-Completeness

Also Known As

TL;DR

Explanation

P (Polynomial time): problems solvable in O(n^k) — sorting, shortest path, spanning tree. NP (Non-deterministic Polynomial): solutions verifiable in polynomial time — the Travelling Salesman Problem, satisfiability. NP-complete: any NP problem can be reduced to it — the hardest problems in NP. If P = NP (unproven), all NP problems would have polynomial-time solutions. Practical implications: NP-complete problems require heuristics, approximations, or exponential algorithms. Examples relevant to software: Boolean satisfiability (SAT — used in compilers, verification), constraint satisfaction (scheduling, routing), and graph colouring (register allocation).

Common Misconception

Why It Matters

Common Mistakes

• Trying to solve NP-complete problems exactly at large scale — use approximation algorithms or heuristics.
• Confusing NP-hard (at least as hard as NP) with NP-complete (NP-hard and in NP).
• Not recognising that many real scheduling and optimisation problems are NP-complete.
• Assuming P != NP is proven — it is the most famous open problem in computer science.

Code Examples

// Exact TSP solver — O(n!) time — impractical at scale:
function tsp(array $cities): int {
    // Try every permutation:
    $minCost = PHP_INT_MAX;
    foreach (permutations($cities) as $route) {
        $minCost = min($minCost, routeCost($route));
    }
    return $minCost;
}
// 20 cities: 20! = 2.4 quintillion permutations — heat death of universe

// Nearest neighbour heuristic — O(n^2), approximation:
function tspApprox(array $cities): array {
    $route   = [$cities[0]];
    $unvisited = array_slice($cities, 1);
    while ($unvisited) {
        $last    = end($route);
        $nearest = array_reduce($unvisited,
            fn($best, $city) => distance($last, $city) < distance($last, $best) ? $city : $best,
            $unvisited[0]
        );
        $route[]   = $nearest;
        $unvisited = array_diff($unvisited, [$nearest]);
    }
    return $route;
}
// Not optimal, but ~25% of optimal — runs in milliseconds for 1000 cities

References

• ↗ https://en.wikipedia.org/wiki/P_versus_NP_problem

Tags

Related Terms