NP hardness

A decision problem is NP-hard if every problem in NP can be translated into it in polynomial time, preserving the yes or no answer. For a quant building an exact optimiser, that classification applies to the whole family of inputs, such as all possible network layouts or all instances of a particular portfolio model. An individual network can be easy to solve even when the general problem is NP-hard.

Imagine monitoring a trading network with at most one monitor per node. A monitor observes every link that touches its node, and each monitor costs the same. In graph terms, a vertex cover is a set of nodes that touches every edge.

In the fictional network below, A, B and C form a triangle, and C is also linked to D. The links AB and CD share no endpoints, so any cover needs at least two monitors. Placing one at A and one at C covers all four links. The decision answer is no at $k=1$ and yes at $k=2$. The optimum is two, with A and C as one optimal placement.

P is the class of decision problems that a deterministic algorithm can solve in polynomial time. NP contains the decision problems whose yes instances have polynomial-length certificates verifiable in polynomial time. For Vertex Cover, the certificate is the list of selected nodes. The verifier checks that the selected nodes belong to the graph and fit the budget, then scans the edges to confirm each has a selected endpoint. The same list certifies feasibility, while optimality also requires ruling out smaller covers. The four-node argument does that for this one network. MIT’s notes on NP-complete problems

To prove a new decision problem $Y$ is NP-hard, start from a known NP-complete problem $X$ and reduce from $X$ to $Y$. The reduction builds an instance of $Y$ from each instance of $X$, with the same yes or no answer. A polynomial-time solver for $Y$ would then solve $X$ in polynomial time. Reversing the arrow would tell you how to solve $Y$ using a solver for $X$. The translation and solver both have to run in time polynomial in their respective encoded input lengths. For the difference between polynomial growth and wall-clock cost, see time complexity. Cook’s formal problem description

Karp's proof starts from Clique, which asks whether a simple undirected graph on $n$ nodes has $k$ pairwise adjacent nodes. A request for more than $n$ nodes is immediately a no instance. For the other instances, make the complement graph by replacing each edge with a non-edge and each missing edge between distinct nodes with an edge. Ask whether this new graph has a vertex cover of size at most $n-k$. A $k$-clique in the original graph has no internal edges in the complement, so the other $n-k$ nodes cover every complement edge. Conversely, the nodes outside such a cover have no edges between them in the complement, so at least $k$ of them form a clique in the original graph. Building the complement takes polynomial time. This argument applies across the whole input family. Karp, Reducibility Among Combinatorial Problems

The decision version of Vertex Cover is therefore NP-complete. It is both NP-hard and in NP. Minimum Vertex Cover is an NP-hard optimisation problem because an exact optimiser would answer the decision question by comparing the minimum to $k$. The term NP-complete applies to the yes-or-no problem. A deterministic polynomial-time exact algorithm for the general minimum-cover problem would imply $P=NP$, which remains an open question. Clay Mathematics Institute

The same distinction matters in sparse portfolio optimisation. A cap on the number of holdings forces the optimiser to choose which assets can have nonzero weights as well as how much to allocate. The cardinality-constrained mean–variance model studied by Bertsimas and Cory-Wright is NP-hard in general. A feasible portfolio found within the time limit is one candidate. For minimisation, the difference between its objective value and a valid lower bound caps the possible improvement. Bertsimas and Cory-Wright, A Scalable Algorithm for Sparse Portfolio Selection

The SelfMadeQuant lesson NP-Complete Problems and Approximation as a Fallback proves a factor-of-two guarantee for a simple vertex-cover algorithm. The preview is public and the full lesson requires membership.