Structural Complexity of One-Factor Sparse Portfolio Selection Exact Algorithms, Parameterized Hardness, and Restricted Circuit Lower Bounds
Davit Gondauri
Abstract
We study exact-cardinality, equally weighted minimum-variance portfolio selection under a one-factor covariance
model supplied in factor form. In the nonnegative homoskedastic regime, selecting the K smallest loadings is
optimal. Allowing strictly positive asset-specific idiosyncratic variances makes the decision problem NP-complete
even with positive integer loadings and a strictly positive-definite covariance matrix; with identity residual
covariance, exactly one negative loading also suffices. We give exact pseudo-polynomial dynamic programs for one
factor and fixed factor dimension and prove W[1]-hardness parameterized by K, including the positive-data family.
Consequently, a general exact polynomial-time algorithm for Monge’s (2017) equally weighted single-factor
variance-input formulation would imply P=NP. For a normalized binary factor encoding, we construct a depth-zero
projection from modular k-SUM that preserves exact cardinality and positive definiteness. The projection transfers
Lin’s (2026) fixed-k circuit lower bound under its stated width and quantifier conditions and, independently, yields
a parity-based proof that the portfolio language is not in nonuniform AC⁰ even with identity residual covariance and
polynomially bounded integer coefficients. These are restricted-circuit results: no unrestricted P/poly lower bound
and no separation of P from NP is claimed.