Structural Complexity of One-Factor Sparse Portfolio Selection: Exact Algorithms, Parameterized Hardness, and Restricted Circuit Lower Bounds

Davit Gondauri

EconStor Preprints from ZBW - Leibniz Information Centre for Economics

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.

Keywords: cardinality-constrained portfolio optimization; factor representation; one-factor covariance; exact algorithms; NP-completeness; pseudo-polynomial time; parameterized complexity; W[1]-hardness; k-SUM; AC⁰; circuit complexity; P/poly; hardness magnification (search for similar items in EconPapers)
JEL-codes: C61 C63 G11 (search for similar items in EconPapers)
Date: 2026
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.econstor.eu/bitstream/10419/343614/1/S ... rtfolio_Gondauri.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:zbw:esprep:343614

Access Statistics for this paper

More papers in EconStor Preprints from ZBW - Leibniz Information Centre for Economics Contact information at EDIRC.
Bibliographic data for series maintained by ZBW - Leibniz Information Centre for Economics ().