Unequal residual variances or one negative loading are enough to destroy the K-smallest-beta sort.
Neither modelling choice is unusual. Allow strictly positive idiosyncratic variances to differ across assets, and the exactly-K equally weighted problem becomes NP-complete even with positive integer loadings and a strictly positive definite covariance. Alternatively, hold residual covariance at the identity and permit exactly one negative loading. The problem is NP-complete again. Gondauri proves both results directly in factor form, taking the triple (β, D, C) as input instead of an n by n matrix. His description of the contribution, "structural and encoding-specific rather than generic", gets the emphasis right.
The paper contains no empirical work and says so plainly: "No empirical dataset is used in this theoretical study." There is no Sharpe, universe or sample period. Every performance number below comes from us. Gondauri's formal results assume that β and D arrive as exact integers or rationals. We estimate them from prices, then discretise the loadings for the dynamic program. Our figures therefore describe a portfolio-construction implementation, rather than measuring any complexity claim made in the paper.
The decision problem and its five consequences
Everything starts from one decision language. Covariance arrives in factor form, Sigma = beta beta' + D, with diagonal D. For a selected set S, equal weights of 1/K make portfolio variance proportional to F(S) = (sum of the selected betas) squared plus the sum of the selected residual variances. The decision question asks whether some set containing exactly K names puts F(S) below a threshold C. Gondauri specifies a canonical binary encoding for the integer triple (beta, D, C). That encoding matters for the later circuit claims, which concern bit strings.
The results then divide into a polynomial corner, two NP-complete families, an exact dynamic program, W[1]-hardness parameterised by K, and a bit-level projection yielding constant-depth circuit lower bounds.
Rank-one quadratic 0-1 hardness itself is established territory, as the paper makes clear. It credits Çela, Klinz and Meyer (2006) with observing NP-hardness at rank one through the subset-sum square objective. The same authors also gave the constant-rank pseudo-polynomial algorithm. Theorem 2 "is not presented as a first rank-one quadratic NP-hardness result." Gondauri's contribution locates the particular modelling choices where hardness enters.
Where sorting still works
Suppose every residual variance equals a common d > 0 and every beta is nonnegative. The optimal exactly-K portfolio then consists of the K smallest loadings and takes O(n log n) comparisons to find. At fixed K, the second term stays constant. The square increases across the nonnegative half-line, leaving no further choice to optimize. In portfolio terms, this is simply a beta sort: estimate the loading for each name, select the bottom K and assign weights of 1/K.
Corollary 2.1 marks the first break. Within the factor-encoded, equally weighted one-factor family, strictly positive residual variances may vary by asset while loadings remain nonnegative. That change makes the family NP-complete. The construction keeps all loadings positive and Σ strictly positive definite.
The signed construction is cleaner. Set D = I, use ordinary loadings H + a_i, and add exactly one anchor at minus (kH + t). With K = k+1 and threshold C = K, an instance is accepted precisely when the chosen loadings sum to zero. Any zero-sum selection has to include the anchor. Exact cardinality then leaves exactly k ordinary items, reducing the remaining choice to subset sum. A single negative-beta name supplies the required cancellation. Gondauri also observes that, for beta beta' + I with nonzero beta, the exceptional eigenvalue is the largest one. The spectral condition in Gao and Li (2013) therefore does not automatically make this signed family tractable.
The positive-data reduction has more machinery. It chooses M = 2ta_max + t^2 + 1 and sets d_i = M - 2ta_i, guaranteeing at least t^2 + 1. By construction, residual variance falls affinely as the loading rises. Theorem 2 uses that opposition to encode subset sum in the objective. Gondauri limits the conclusion carefully: "This is a family-level structural boundary: it does not claim that every instance with unequal idiosyncratic variances is hard."
What does NP-complete cost at K = 10?
Less than the label might suggest. The abstract acknowledges this immediately, promising "exact pseudo-polynomial dynamic programs for one factor and fixed factor dimension." For the positive-integer family, the dynamic program tracks states indexed by cardinality and loading sum. It solves the problem exactly with O(nKB) transitions and O(KB) stored entries, where B denotes the sum of loadings. Its bit cost is O(nKB·poly(L)). The family is consequently weakly NP-complete. Corollary 3.1 adds that, unless P=NP, it is not strongly NP-hard when magnitudes are polynomially bounded.
W[1]-hardness carries more weight for implementation. A common response to exact cardinality is that K stays small, perhaps ten or twenty names, making branch-and-bound search manageable. Theorem 4 preserves the parameter exactly as K = k. Its source problem is bounded zero-sum k-SUM, asking whether exactly k listed integers total zero. Those integers have magnitude at most n^(2k), requiring O(k log n) bits. Under FPT ≠ W[1], no algorithm can run in f(K) times a fixed power of the input length. Small K alone supplies no general exact method.
Corollary 3.1 also identifies the available escape. Polynomially bounded magnitudes keep the dynamic program's state space under control. Whether loadings and residual variances estimated from actual cross-sections occupy that range is an empirical question. The paper offers no data to answer it.
Corollary 2.2 resolves an open question posed by Monge (2017, Appendix, p. 22): whether the equally weighted, cardinality-constrained single-factor problem has a polynomial solution. Under the general binary-encoded variance-input formulation, a general exact polynomial-time algorithm would imply P=NP. Particular subclasses remain polynomially solvable, including Theorem 1's nonnegative homoskedastic regime. To my eye, this is the paper's more useful contribution.
Circuit claims, tightly bounded
Gondauri gives a depth-zero projection from modular k-SUM, the problem of finding some k residues whose sum is zero modulo 2^b. The resulting instance contains n+k assets, has K' = k+1, assigns every residual variance 1, and uses threshold k+1. Loading width is 1 + ceil(log2((2k-1)Q)), where Q = 2^b. Each output bit copies either a source bit or a constant.
Now set n = k = t and b = 1. The target contains 2t assets, with loadings 2 + y_i, anchors -2(t+q), coefficient magnitudes O(t) and total length Θ(t log t). Acceptance matches the parity of the input bits. The language therefore lies outside nonuniform AC⁰.
The paper itself says, "A polynomial-time algorithm and an AC⁰ lower bound are fully compatible," while pointing out that the parity instances remain polynomial-time solvable through the signed dynamic program. My judgement is that this offers a trading desk nothing. The fixed-k quantitative lower bound of (n/k)^(η(k−1)) gates depends entirely on Lin (2026), an ECCC preprint at Revision 2. It carries over that paper's width, depth and onset conditions, all identified in the scope section. Gondauri keeps the boundary explicit: "no unrestricted P/poly lower bound and no separation of P from NP is claimed."
Our market run
The theory begins with supplied factor inputs. Our run estimates them through a rolling window.
We constructed an exact-K portfolio monthly from the top 50 US stocks by trailing one-year dollar volume. The portfolio holds K = 10 names at equal 10% weights and rebalances at the first trading day's closing auction. Its window runs from 2020-01-01 to 2024-07-01. Each month, we regress 252 days of daily returns against SPY and require 200 complete paired observations. We define beta_i as the regression slope scaled by daily SPY standard deviation, with d_i equal to residual variance. We then minimize F(S) exactly.
Loadings are integerized at a scale of 1000. The dynamic program has a state guard of 2,000,000 entries, while enumeration stops at 1,000,000 subsets. There are roughly 10.3 billion ways to choose 10 names from 50, so exhaustive search never runs. We validate the traded support against the unrounded global optimum. Every fill incurs commissions of $0.0040 per share, subject to a $1.00 order minimum. Slippage is zero because execution uses market-on-close orders at the auction print.
Over the window, the pass returned 50.46% in total. Sharpe was 0.65, annualised volatility 17.26%, and maximum drawdown -24.30% (Sortino 0.85, Calmar 0.39). Those figures are ours, generated by one automated pass across one window. Gondauri reports no performance results, leaving no paper figure for comparison.
They describe our implementation first. The choices likely to matter most were ours: a 50-name mega-cap universe, K = 10, long-only equal weighting at 1.0x gross, and a one-year daily estimation window spanning both March 2020 and 2022.
The portfolio construction does expose the trade-off used by Theorem 2. When estimated betas are all positive, the squared-sum term favours the ten lowest-beta names. Theorem 1 proves that sort optimal when residual variances are equal. Combinatorial optimization only helps when residual variances differ enough for a higher-beta name with lower residual variance to deserve a place. Theorem 2 encodes subset sum through this same exchange. Theorem 6 reaches hardness another way: every residual variance equals 1, while one negative loading drives the construction.
We have previously written about minimum-variance portfolios swallowing whichever selection rule is attached to them (our note on Bouzguenda and Jarboui). This one automated pass gives no evidence that exact cardinality changes that outcome.
Approximation hardness would make the theoretical result bind more directly in practice, and the paper says it does not establish any. Another route would show that estimated (β, d) pairs from real cross-sections create dynamic-program states that exceed memory at plausible universe sizes. Neither appears here. Gondauri does provide a clean account of the modelling choices that eliminate the sort, including the striking case of a single short leg.
Our backtest stops at 2024-07-01, and everything after that date is deliberately left untouched so the same strategy can be checked out of sample later.