Paper: arXiv 2603.15652

Authors: Davit Gondauri

Abstract

This paper makes the Millennium Prize problem P vs NP operational in quantitative finance by studying cardinality-constrained portfolio selection. Starting from the convex Markowitz mean-variance program with CAPM-based expected returns (Rf plus beta times ERP), we impose a hard sparsity rule that limits the portfolio to K assets out of approximately 94 industry portfolios (Damodaran). The constraint couples discrete subset selection with continuous weight optimization, yielding a mixed-integer quadratic program and an NP-hard search space that grows combinatorially with n and K. We therefore evaluate scalable approximation schemes (greedy screening, Monte Carlo sampling, and genetic algorithms) under a replication-oriented protocol with random-seed control, distributional performance summaries (median and quantiles), runtime profiling, and convergence diagnostics. Dependence structure is documented via correlation and covariance diagnostics and positive-semidefinite checks to link algorithm behavior to the geometry implied by the risk matrix. To support the title’s derivatives component, we add a European call option priced by the Black-Scholes model and map it into CAPM-consistent moments using delta-based linearization, validated with a bump test and moneyness/maturity sensitivity. Results highlight how the cardinality constraint reshapes the attainable efficient frontier, why stability and computational-cost trade-offs matter more than single-best runs, and how common-factor dependence can limit diversification in K-sparse solutions. The study provides a reproducible template for NP-hard portfolio optimization with transparent inputs and extensible derivative overlays.

Complexity vs Empirical Score

  • Math Complexity: 6.5/10
  • Empirical Rigor: 6.0/10
  • Quadrant: Holy Grail — high math complexity, high empirical rigor

Why this score: The paper provides a formal theoretical framing of cardinality-constrained portfolio optimization within NP-hardness complexity, backed by solid single-index covariance and Black-Scholes delta-mapping mathematics. It features a well-structured empirical workflow using Damodaran industry datasets with strong emphasis on algorithmic stability, runtime profiling, and seed-controlled reproducibility.

Research Flowchart

  flowchart TD
    A[Research Goal: Operationalize P vs NP in Portfolio Optimization via Cardinality Constraints] --> B[Inputs: Damodaran Industry Portfolios, CAPM Parameters, & Black-Scholes Call Option]
    B --> C[Problem Formulation: Mixed-Integer Quadratic Program coupling Discrete Selection & Weight Optimization]
    C --> D[Approximation & Diagnostics: Greedy, Monte Carlo, & GA with PSD Diagnostics & Delta Linearization]
    D --> E[Key Findings: Quantified Frontier Shifts, Runtime-Stability Trade-offs, & Factor-Limited Diversification]