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

Davit Gondauri

REVIEW

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

Davit Gondauri

Econometrics · Submitted 15 Sep 2026 · 4 references

Pith's verdict: Solid NP-completeness and AC⁰ lower bound for a specific portfolio model; standard techniques but carefully executed and honestly scoped.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on September 18, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 3 major objections · 5 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2609.17626 (version 1)

Pith IDVSBMRGVO, Pith's permanent record of this paper and its review

CitationDavit Gondauri. "Structural Complexity of One-Factor Sparse Portfolio Selection: Exact Algorithms, Parameterized Hardness, and Restricted Circuit Lower Bounds." arXiv:2609.17626 (2026). https://pith.science/paper/VSBMRGVO

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

Here’s my read on the Gondauri paper.

What’s new: The NP-completeness for the positive-integer, equal-weight, one-factor exact-cardinality portfolio problem, with strict positive definiteness. Both the homoskedastic tractable regime and the D=I signed case sharpen the boundary. The AC⁰ lower bound via parity projection is clean and obviously correct. The paper also provides a W[1]-hardness reduction that preserves K and keeps parameters positive, plus a pseudo-polynomial DP that shows weak NP-completeness. It answers Monge’s 2017 question decisively for the factor-encoded formulation.

What the paper does well: The reductions are spelled out with exact equations. The encoding conventions are stated up front, so the circuit lower bounds rest on a precise bit model. The paper is unusually explicit about its limitations—it never claims a general P/poly barrier, and it separates the fixed-k quantitative bound from the full-language AC⁰ nonmembership. The author cites competing work fairly and does not oversell. The writing is clear and self-contained.

Soft spots: The technical novelty is incremental rather than groundbreaking. Every major technique (Subset Sum completion, k-SUM parameterized reduction, parity-based AC⁰ separation) is standard. The fixed-k circuit transfer depends on Lin’s 2026 ECCC result, which is still relatively fresh. The pseudo-polynomial DP is textbook. Still, the paper’s contribution is the specific portfolio-model classification, not a new algorithmic principle. There is no deep combinatorial insight; instead, it is a well-executed application of known tools to a well-motivated problem. The W[1]-hardness reduction is essentially a shift, which is fine but not surprising.

Who this is for: Researchers in portfolio optimization who want to know whether exact solutions are possible under factor-model assumptions, and complexity theorists looking for a concrete language with both an NP-completeness result and a non-AC⁰ lower bound that does not rely on unproven separations. The paper will be useful to both groups.

Recommendation: The paper is sound, honest, and worth publishing. I would recommend acceptance with minor revisions—perhaps checking the width calculations in Theorem 7 to ensure the canonical encoding matches the explicit bound stated. It deserves a serious referee and a place in a good theory journal.

In short: a careful piece of work that does exactly what it claims.

Referee report

Significance

If the results hold, the paper provides a clean complexity map for a narrow, practically motivated portfolio model: a sharp tractability/hardness boundary inside the one-factor equal-weight class, parameter-preserving W[1]-hardness, a weakly NP-complete regime with a matching pseudo-polynomial algorithm, and two restricted circuit consequences. The proofs are explicit, self-contained except for the external k-SUM and AC^0 source theorems, and the claims are scoped with unusual care: the factor-form input language is distinguished from the explicit-covariance language, the canonical encoding is defined rigorously, Corollary 7.1 and 7.2 are correctly presented as different regimes, and Proposition 8 is not oversold as a new barrier result. The paper is honest about its limitations and does not claim first rank-one NP-hardness, a new parity lower bound, or progress on P/poly.

Major objections (3)

[Section 3, Theorem 2, Eq. (4)] The reduction is correct as written: with M = 2t·a_max + t² + 1 and d_i = M − 2t·a_i, positivity d_i ≥ t² + 1 > 0 holds, and F(S) = (s−t)² + kM − t² gives F(S) ≤ C iff s = t. Since the source problem (Lemma 2.1) is weakly NP-complete and the constructed magnitudes have polynomial binary length, the subsequent claim of weak NP-completeness in Corollary 3.1 is consistent, not a contradiction. I verified the boundary case s = t exactly; no issue found.
[Section 5, Theorem 4] The parameter-preserving reduction relies on the stated W[1]-completeness of distinct-index zero-sum k-SUM with integers bounded by n^{2k}, cited to Abboud, Lewi, and Williams. Since the manuscript's other central results (Theorems 2, 3, 6, 7, Corollary 7.2) do not depend on this source, even if the exact provenance of that W[1]-completeness statement required adjustment, Theorem 4 is the only affected claim. The reduction itself, shifting by A = R+1 and applying Theorem 2 with K = k, is internally consistent and preserves the parameter exactly.
[Section 8, Corollary 7.2] The parity argument is sound: instantiating Theorem 7 with n = k = t and b = 1, the only t-subset is the whole source list, so acceptance means the number of 1 bits is even, i.e., the parity predicate. The target width Wβ = 1 + ⌈log₂((2k−1)Q)⌉ correctly fits all ordinary loadings in [Q, 2Q−1] and all anchors −(k+q)Q; the output length N(t) = Θ(t log t) with coefficients O(t) verifies the constant-depth polynomial-size contradiction with Furst–Saxe–Sipser. The separation between the fixed-k regime (Corollary 7.1) and the k = n parity regime is explicitly and correctly maintained.

Minor objections (5)

[Section 1.1] The canonical encoding is defined precisely, but the sentence 'This is the only prefix code used in the header' could be expanded by one clause noting that nat is self-delimiting; as written it is clear from the definition, so this is purely stylistic.
[Section 2, Theorem 1] The proof says 'the square is increasing on [0,∞)', which is correct because all β_i are nonnegative. Perhaps state explicitly that the sum of selected loadings is therefore nonnegative, since the argument would require modification otherwise.
[Section 9, Proposition 8] The circuit-size model and the length-selection multiplexer are described correctly. A small clarification would help: the statement 'a polynomial-size circuit computes R_A(x) together with its output length ℓ' relies on the standard fact that a polynomial-time computable function has polynomial-size circuits; this is standard but worth a parenthetical.
[Throughout] Minor typographical inconsistencies in the OCR-like rendering (e.g., 'idiosy ncratic', 'loadi ngs', 'Th eorems') appear in the submitted text; these should be cleaned in the final version.
[Section 12.2] The novelty positioning is admirably restrained; consider moving the explicit acknowledgment that 'Theorem 2 is not presented as a first rank-one quadratic NP-hardness result' into Section 1.3, where the reader first encounters the contribution list.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

Selecting an equally weighted one-factor portfolio is NP-complete when asset-specific risks vary and provably hard for constant-depth circuits.

The reading

This paper studies the exact-cardinality, equally weighted minimum-variance portfolio selection problem under a one-factor covariance model. It establishes a sharp structural boundary: when all assets share the same residual variance and loadings are nonnegative, the optimal subset is found by sorting the loadings. In contrast, allowing asset-specific positive residual variances or introducing a single negative loading makes the decision problem NP-complete. The paper further provides exact pseudo-polynomial dynamic programs, proves that the problem is W[1]-hard when parameterized by the cardinality K, and constructs a bit projection from modular k-SUM that yields unconditional lower bounds for constant-depth circuits ($AC^{0}$). These results together map the complexity landscape of a practically motivated portfolio formulation.

What carries the argument

The key machinery consists of two parts. First, a completion-of-the-square reduction from Exact Subset Sum transforms a subset-sum instance into a portfolio instance by setting the objective $F(S)=(\sum\beta_i)^2+\sum d_i = (s-t)^2 + \text{constant}$, where $d_i$ are chosen to depend on the loadings and the target $t$. This identity turns the subset-sum decision into a portfolio decision. Second, for the circuit lower bounds, a depth-zero projection from modular k-SUM to a restriction with $D=I$ ensures that every output bit is either a source bit or a constant. This construction connects the portfolio language to known hardness results for k-SUM and parity, yielding $AC^{0}$ hardness.

Extended reading notes

Core claim

The central discovery is that a very restricted version of the portfolio selection problem—exactly K equally weighted assets, factor-form covariance, integer data—has a complex frontier. It is solvable by sorting when residual variances are equal and loadings nonnegative, but becomes NP-complete when residual variances differ (even all positive) or when exactly one loading is negative (with identity residual covariance). Moreover, the problem is not solvable by nonuniform $AC^{0}$ circuits, a lower bound that holds even for polynomially bounded integer coefficients. This shows that the binary encoding of the factor data can induce computational hardness even in regimes where the numerical magnitudes are small, and it provides a concrete portfolio model that separates constant-depth circuit classes from polynomial-time computation.

Load-bearing premise

The NP-completeness reductions assume the covariance matrix is given in factor form (beta, D) rather than as an explicit matrix; if the covariance were supplied entry-by-entry, the reductions might fail because forming pairwise products beta_i beta_j would require arithmetic that the bit projection from modular k-SUM cannot directly implement.

Editorial extensions

If this is right

The NP-completeness of the positive-integer one-factor family (Theorem 2) implies that Monge's (2017) exact equal-weight cardinality-constrained single-factor optimization formulation is NP-hard, settling an open question he posed.
The W[1]-hardness result (Theorem 4) shows that no algorithm with running time $f(K)\cdot \text{poly}(n)$ exists unless FPT = W[1], placing the problem in the same parameterized hardness class as k-SUM.
The AC^0 nonmembership (Corollary 7.2) proves that even for polynomially bounded integer coefficients, no constant-depth polynomial-size circuit can decide the portfolio language, establishing a concrete separation between constant-depth circuits and polynomial-time algorithms for a natural optimization problem.
The pseudo-polynomial dynamic program (Theorem 3) shows the problem is weakly NP-complete, meaning that under non-encoded numerical magnitudes the problem is not strongly NP-hard.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Because the AC^0 lower bound applies to instances with polynomially bounded coefficients, any heuristic that relies on a bounded-depth circuit (e.g., shallow neural networks) would provably fail on worst-case inputs of this portfolio problem. This suggests that practitioners seeking exact solutions may need to use deeper or recurrent inference structures or accept exponential time.
The depth-zero projection is unusually transparent: every output bit is either a source bit or a constant. This structural simplicity makes the portfolio language attractive as a test case for hardness-magnification frameworks, where modest AC^0 lower bounds could, in principle, be amplified to stronger circuit lower bounds via meta-complexity connections—a possibility the paper explicitly leaves
The coexistence of weak NP-completeness (hence a pseudo-polynomial algorithm) with AC^0 hardness is noteworthy: it shows that a problem can be polynomial-time solvable in the numerical sense (when magnitudes are small) yet require super-constant circuit depth when the data is encoded in binary. This tension underscores how encoding conventions shape circuit complexity.

Original 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^0 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.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 6,381 input tokens.

What the abstract itself states, as probabilities: claims first 0.06 · states limitation 0.97 · human participants 0.01 · controlled comparison 0.02 · randomized assignment 0.01 · states quantitative result 0.62 · compares with prior results 0.80 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

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^0 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.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	We study exact-cardinality, equally weighted minimum-variance portfolio selection under a one-factor covariance model supplied in factor form.	contribution 0.59	0.75	0.04	asserted 0.90
s1	In the nonnegative homoskedastic regime, selecting the K smallest loadings is optimal.	result 0.98	0.66	0.05	asserted 1.00
s2	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.	result 1.00	0.77	0.25	asserted 1.00
s3	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.	contribution 0.72	0.95	0.23	asserted 1.00
s4	Consequently, a general exact polynomial-time algorithm for Monge's (2017) equally weighted single-factor variance-input formulation would imply P=NP.	interpretation 0.92	0.63	0.42	asserted 0.95
s5	For a normalized binary factor encoding, we construct a depth-zero projection from modular k-SUM that preserves exact cardinality and positive definiteness.	method 0.71	0.92	0.04	asserted 1.00
s6	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^0 even with identity residual covariance and polynomially bounded integer coefficients.	result 0.81	0.84	0.16	asserted 1.00
s7	These are restricted-circuit results: no unrestricted P/poly lower bound and no separation of P from NP is claimed.	limitation 0.99	0.61	0.09	asserted 1.00

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

References

Works cited (4)

[1]

Abboud, A., Lewi, K., & Williams, R. (2014). Losing Weight by Gaining Edges. In Algorithms – ESA 2014 (LNCS 8737, pp. 1–12). Springer. https://doi.org/10.1007/978-3-662-44777-2_1 Aaronson, S., & Wigderson, A. (2009). Algebrization: A new barrier in complexity theory. ACM Transactions on Computation Theory, 1(1), Article

View on Pith doi:10.1007/978-3-662-44777-2_1 2014
[2]

https://doi.org/10.1145/1490270.1490272 Anis, H. T., & Kwon, R. H. (2025). End -to-end, decision-based, cardinality-constrained portfolio optimization. European Journal of Operational Research, 320(3), 739–753. https://doi.org/10.1016/j.ejor.2024.08.030 Baker, T., Gill, J., & Solovay, R. (1975). Relativizations of the P =? NP question. SIAM Journal on Com...

View on Pith arXiv 2025
[2026]

https://eccc.weizmann.ac.il/report/2026/139/ Monge, J. F. (2017). Cardinality constrained portfolio selection via factor models. arXiv:1708.02424v1. https://arxiv.org/abs/1708.02424v1 Monge, J. F. (2020). Equally weighted cardinality constrained portfolio selection via factor models. Optimization Letters, 14, 2515–

View on Pith Pith review arXiv 2017
[2538]

https://doi.org/10.1007/s11590-020-01571-6 Murray, C. D., & Williams, R. R. (2017). On the (Non) NP-Hardness of Computing Circuit Complexity. Theory of Computing, 13(4), 1–22. https://doi.org/10.4086/toc.2017.v013a004 Oliveira, I. C., Pich, J., & Santhanam, R. (2021). Hardness Magnification Near State-of-the-Art Lower Bounds. Theory of Computing, 17(11), ...

View on Pith arXiv 2017

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.

[1] [1]

Abboud, A., Lewi, K., & Williams, R. (2014). Losing Weight by Gaining Edges. In Algorithms – ESA 2014 (LNCS 8737, pp. 1–12). Springer. https://doi.org/10.1007/978-3-662-44777-2_1 Aaronson, S., & Wigderson, A. (2009). Algebrization: A new barrier in complexity theory. ACM Transactions on Computation Theory, 1(1), Article

View on Pith doi:10.1007/978-3-662-44777-2_1 2014

[2] [2]

https://doi.org/10.1145/1490270.1490272 Anis, H. T., & Kwon, R. H. (2025). End -to-end, decision-based, cardinality-constrained portfolio optimization. European Journal of Operational Research, 320(3), 739–753. https://doi.org/10.1016/j.ejor.2024.08.030 Baker, T., Gill, J., & Solovay, R. (1975). Relativizations of the P =? NP question. SIAM Journal on Com...

View on Pith arXiv 2025

[3] [2026]

https://eccc.weizmann.ac.il/report/2026/139/ Monge, J. F. (2017). Cardinality constrained portfolio selection via factor models. arXiv:1708.02424v1. https://arxiv.org/abs/1708.02424v1 Monge, J. F. (2020). Equally weighted cardinality constrained portfolio selection via factor models. Optimization Letters, 14, 2515–

View on Pith Pith review arXiv 2017

[4] [2538]

https://doi.org/10.1007/s11590-020-01571-6 Murray, C. D., & Williams, R. R. (2017). On the (Non) NP-Hardness of Computing Circuit Complexity. Theory of Computing, 13(4), 1–22. https://doi.org/10.4086/toc.2017.v013a004 Oliveira, I. C., Pich, J., & Santhanam, R. (2021). Hardness Magnification Near State-of-the-Art Lower Bounds. Theory of Computing, 17(11), ...

View on Pith arXiv 2017