Tax-loss harvesting is NP-complete
A taxable account holds lots, shares of one security bought together at one price. Selling a lot whose price has fallen realizes a loss, which offsets gains on the year's return, and costs some tracking error or turnover once the proceeds are reinvested. Tax-loss harvesting chooses which lots to sell. With whole shares, the choice is NP-complete.
Definition (TLH). Lots \(1, \dots, n\); lot \(i\) has an unrealized loss \(\ell_i \ge 0\) and a tracking cost \(d_i \ge 0\); a tracking budget \(D\); a loss target \(T\). A lot is sold whole or kept. Is there a set \(S \subseteq \{1, \dots, n\}\) with
\[\sum_{i \in S} \ell_i \ge T \quad\text{and}\quad \sum_{i \in S} d_i \le D \,?\]Any harvesting formulation with a risk or turnover budget contains TLH as the case in which every other constraint is slack. NP-completeness is a property of decision problems; the optimization problem, maximize the loss within the budget, is then NP-hard.
Theorem. TLH is NP-complete.
Proof. TLH is in NP: given a proposed set \(S\) of lots to sell, we can check that its total loss reaches \(T\) and its total tracking cost stays within \(D\). The set \(S\) is called a certificate, meaning a proposed solution we can verify. Checking it requires \(O(n)\) additions and two comparisons.
It is NP-hard because it is the 0–1 knapsack decision problem with the words changed: loss is value, tracking cost is weight, the tracking budget is the capacity and the loss target is the value target. Knapsack is NP-complete, and the identity map is a polynomial-time reduction. ∎Knapsack is problem MP9 of M. R. Garey and D. S. Johnson, Computers and Intractability (Freeman, 1979); its special case \(\ell_i = d_i\), \(T = D\) is the KNAPSACK of R. M. Karp, "Reducibility among combinatorial problems" (1972), which is Subset Sum.
Proof (from Subset Sum). Given positive integers \(a_1, \dots, a_n\) and a target \(B\), Subset Sum asks whether some subset sums to exactly \(B\). Build \(n\) lots: lot \(i\) is one share priced at \(a_i\) with cost basis \(2a_i\), so \(\ell_i = a_i\), and its tracking cost is the dollars it moves, \(d_i = a_i\). Set \(T = D = B\). If \(\sum_{i \in S} a_i = B\), then \(S\) is feasible. If \(S\) is feasible, then \(B = T \le \sum_{i \in S} \ell_i = \sum_{i \in S} a_i = \sum_{i \in S} d_i \le D = B\), so \(\sum_{i \in S} a_i = B\). The construction takes linear time. ∎
Remark (Quadratic risk). Replace \(\sum_i d_i x_i \le D\) by \(x^\top \Sigma x \le D\) with \(\Sigma = \operatorname{diag}(a_1, \dots, a_n)\). For binary \(x\), \(x_i^2 = x_i\), so nothing changes.
Remark (Source of hardness). The hardness is the discreteness. With fractional shares, no minimum ticket and no fixed cost per trade, the problem is a fractional knapsack, solved greedily by \(\ell_i / d_i\), or under quadratic risk a convex program; both are polynomial. Whole shares, minimum lot sizes, per-ticket costs or cardinality limits each restore the integrality. The tax is not the source.