P vs NP & NP-Completeness
debt(d7/e7/b5/t7)
Closest to 'only careful code review or runtime testing' (d7). The detection_hints list Blackfire (a profiler) and note automated detection is 'no'; the code pattern (brute-force O(n!) or O(2^n) on large inputs) is only visible when a developer recognises the problem class and its scaling behaviour — Blackfire can show the symptom (slow runtime) but cannot identify the cause as NP-completeness. No linter or SAST will flag it.
Closest to 'cross-cutting refactor across the codebase' (e7). The quick_fix says to switch to heuristics, approximation algorithms, or dynamic programming — but this is not a one-line fix. Replacing an exact NP-complete solver with an approximation or heuristic requires redesigning the algorithm, validating that the approximate solution is acceptable for the business domain, and potentially touching every call site and downstream consumer of the solution. This regularly spans multiple files and components.
Closest to 'persistent productivity tax' (b5). The applies_to covers both web and cli contexts broadly. Choosing an exact solver for an NP-complete problem imposes ongoing drag: future developers must understand why performance degrades at scale, why input is bounded, and why approximate answers are used — but the impact is scoped to the problem domain rather than shaping the entire system architecture.
Closest to 'serious trap' (t7). The canonical misconception (NP means non-polynomial/intractable) directly contradicts the actual definition (Non-deterministic Polynomial = verifiable in polynomial time). Additionally, common mistakes include not recognising real-world scheduling and optimisation problems as NP-complete, and assuming P≠NP is proven. These are systematic conceptual errors a competent developer unfamiliar with complexity theory will reliably make.
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