Parameterized complexity

Parameterized complexity is a framework in computational complexity theory that analyzes problems by separating the input size n from a structural parameter k. Rather than asking whether a problem is polynomial-time solvable, parameterized complexity asks whether the exponential blowup can be confined to the parameter alone. A problem is fixed-parameter tractable (FPT) if it can be solved in time f(k)·n^c for some computable function f and constant c. This reframes hardness: many NP-complete problems, including vertex cover and planar dominating set, are FPT when parameterized by solution size or treewidth, while clique and dominating set are W[1]-hard and believed not to be FPT. Parameterized complexity is the complexity theory of structure — it asks not how large the problem is, but how deeply the hardness is embedded in its organization.\n\nSee also: Kernelization, Treewidth.