P vs NP Problem in Portfolio Optimization: Integrating the Markowitz–CAPM Framework with Cardinality Constraints and Black–Scholes Derivative Pricing

This study develops an integrated economic–computational framework for portfolio construction that makes the P versus NP divide operational within a financially auditable Markowitz–CAPM setting. Starting from the convex mean–variance program, we impose a hard cardinality constraint |supp(w)| ≤ K, which couples discrete subset selection with continuous weight optimization and yields a mixed‑integer quadratic program (MIQP). To ensure empirical transparency, the asset universe is built from approximately n≈94 U.S. industry portfolios from Aswath Damodaran, using levered betas and annualized equity volatilities to calibrate expected returns via μ_i = R_f + β_i·ERP and to construct a fully reconstructible covariance matrix through a single‑index (market‑model) structure. Because the resulting search space grows combinatorially (≈C(n, K)), the paper treats scalable optimization as an approximation problem and evaluates practical solution schemes—greedy screening, Monte Carlo sampling over K‑subsets, and genetic algorithms—under a replication‑oriented protocol with random‑seed logging, distributional performance reporting (median/IQR/quantiles), convergence/effort curves, and runtime profiling. Dependence diagnostics (median pairwise correlation, tail correlation shares, eigenvalue concentration, PSD checks) are reported as first‑class outputs to connect algorithmic behavior to the geometry implied by Σ. To support financial realism beyond linear assets, the framework is extended to a derivative‑augmented universe by embedding a Black–Scholes European call as an additional instrument, mapped into CAPM‑consistent moments via delta‑based linearization and validated by moneyness–maturity robustness and a bump test (delta vs. repricing). Results demonstrate that (i) the hard cardinality rule materially reshapes attainable efficient frontiers and induces discontinuities relative to the unconstrained benchmark; (ii) heuristic performance must be assessed by stability and compute‑cost trade‑offs rather than single best‑run outcomes; and (iii) under a single‑index covariance, strong common‑factor dependence limits diversification, explaining why high‑β industries and clustered sectors may co‑appear in K‑sparse solutions. Overall, the paper provides a journal‑grade, reproducible template for studying NP‑hard portfolio selection with transparent inputs and extensible derivative overlays.