parameterized complexity
Classical complexity asks one blunt question: how does the running time grow with the input size n? But two NP-hard problems of the same input size can feel completely different in practice, because what really makes them hard is some small extra quantity. Parameterized complexity refines the question by separating the input size n from a second 'parameter' k that measures the part of the input responsible for the difficulty — and asks whether the blow-up can be confined to k alone.
The central good news is fixed-parameter tractability (FPT). A problem is FPT if it can be solved in time f(k) times a polynomial in n, where f(k) may be huge (even exponential in k) but the dependence on the input size n stays polynomial, with k kept out of the exponent of n. The payoff is enormous when k is small: f(k) times n is fast even for big n, as long as k is modest. Contrast a brute-force n^k (where k sits in the exponent of n, exploding as the input grows) with an FPT 2^k times n (where the exponential is locked onto the small parameter). Not every problem is FPT; the W-hierarchy (W[1], W[2], ...) classifies the apparently-not-FPT problems, with W[1]-hardness playing the role of 'probably not fixed-parameter tractable' just as NP-hardness signals 'probably not polynomial'.
This is one of the most practically fertile branches of modern complexity, because real inputs often have small natural parameters: the number of variables to delete, the treewidth of a network, the size of a solution you will accept. Vertex cover is the poster child — finding a cover of size k is FPT (solvable in about 2^k times polynomial time), so it is easy whenever you only seek a small cover, even on a huge graph. The framework turns a coarse 'NP-hard, give up' into a sharper 'NP-hard in general, but tractable when this specific parameter is small'.
k-Vertex Cover: does a graph have a cover of k vertices? A naive search tries all subsets, hopeless. The FPT trick: pick any edge; one of its two endpoints must be in the cover, so branch into two cases and recurse with k reduced by 1. The branching tree has depth k and width 2, giving about 2^k times polynomial time — fast for k = 10 even on a million-node graph.
FPT locks the exponential blow-up onto a small parameter k, keeping the dependence on input size polynomial.
FPT (f(k) times polynomial in n) is strictly the goal; an algorithm running in n^k is NOT fixed-parameter tractable even though it is polynomial for each fixed k, because k sits in the exponent of n and the cost explodes as the input grows.