A Landscape Classification Framework for NP-Hard Problems: From Reconnaissance to Algorithm Selection

We propose a unified classification framework for NP-hard problems based on loss landscape topology. The framework classifies 95% of known NP problems into seven boxes (combinatorial optimisation, graph theory, logical satisfaction, path/network, permutation/assignment, sequential decision, miscellaneous), further divided into 24 sub-boxes each with formal objective functions. A three-tier reconnaissance system (aerial survey, scout sampling, mass sampling) analyses landscape topology before algorithm selection. A five-cut decision tree maps landscape properties to optimal solvers and parameter configurations. All 22 sub-boxes are exhaustively enumerated with default algorithms, scout-based adjustments, and landscape-based parameter settings. Box 6 (sequential decision) is fully validated using MCCO as proof of concept, demonstrating 3. 56× speedup via landscape-guided deployment. The framework draws an analogy to database normalisation: just as complex data can be decomposed through finite normal forms, complex NP problems can be classified through finite landscape cuts. ORCID: 0009-0002-9497-1336. v2 (2026-04-11): Expanded Related Work with six existing frameworks (Garey added cross-framework comparison table; references expanded from 12 to 16. v3 (2026-04-11): Added Scout-Based Algorithm Adjustment and Landscape-Based Parameter Configuration (22 sub-boxes exhaustively enumerated with reconnaissance-based overrides and full parameter lookup tables) ; Landscape Transformation section (8 transformation methods, 4 difficulty scores, 4-layer stopping conditions with marginal benefit and ROI analysis, precision recovery) ; Statistical Foundations of Reconnaissance (Type I/II error rates, Power Analysis for scout count, Bonferroni correction, effect size estimation, GP uncertainty propagation) ; AI-Executable Protocol discussion; three-layer acceleration conclusion (reconnaissance × transformation × AI execution) ; TSP worked example with three-way comparison (brute force vs blind default vs framework-guided, 0. 006s solve time) ; Scaling test (10/20/50 cities) with "How Close to P? " comparison table (framework at 10⁶ vs brute force at 10⁶⁴) ; Limitations expanded to 8 items. v4 (2026-04-12): Three new chapters: Landscape Cutting (Decomposition): cutting principles, five cutting tools, six-box cuttability table, transform-first-then-cut ordering, parallel deployment pipeline with global refinement, five cutting considerations. The Evaluation Matrix: 9 transformations × 4 cuts = 36-cell exhaustive evaluation; empirical validation on 100-city TSP (12 cells in 3. 37s) ; cutting quality check with exhaustibility guarantee. Algorithm Adequacy Scoring: scale × difficulty → four-tier minimum tool level. Cross-box empirical validation (six boxes, all new): Box 1b TSP: TSPLIB standard benchmarks (eil51/berlin52/kroA100), equal-time-budget fair comparison, framework wins by 4–8% gap reduction. Box 1a MKP: Multidimensional knapsack (50–500 items, 3–10 constraints), framework wins by 1. 4–6. 9%, Chu TSPLIB scaling evidence added. References: 16 → 18 (added Reinelt 1991 TSPLIB, Chu transformation and cutting are execution. Score Significance Testing (new Section 10. 5): When exhaustive evaluation ranks two cells with similar scores, sampling noise may reverse the ranking. New protocol: paired tt t-test (or Wilcoxon) on top two cells using existing reconnaissance data; significant → deploy winner; not significant → deploy simpler configuration (fewer transformations, fewer cuts). Cost: zero (arithmetic on already-computed data). Only top-two comparison needed (a fortioria\ fortiori a fortiori guarantee for all lower ranks). Three-layer statistical discipline Remark: Reconnaissance layer controls score accuracy (Type I/II, power analysis, Bonferroni, GP uncertainty). Exhaustion layer eliminates selection error (all 36 cells evaluated). Decision layer controls ranking error (score significance test when differences are small). Defence-first philosophy formally shown to pervade all three layers, not just reconnaissance. References de-duplicated: removed duplicate entries for Rice (1976) and Wolpert Box 2b split into 2b-i (Vertex Cover and Set Cover, admitting constant-factor or logarithmic approximations via LP rounding) and 2b-ii (Dominating Set, admitting no constant-factor approximation unless P=NP) ; Classification Principle amended to state that sub-box boundaries are determined by landscape structure and approximation hardness rather than superficial semantic similarity. (3) Universality claim tightened — replaced "covers 95% of known NP problems" with "spans all major structural types of NP-hard problems catalogued in Garey added new subsection classifying eight modern NP-hard problems (Neural Architecture Search, Hyperparameter Optimisation, Graph Neural Network subgraph matching, Federated Learning client selection, Quantum Circuit Compilation, Blockchain Shard Assignment, Data-centre VM Placement, Model Merging) to demonstrate that the taxonomy extends naturally to problems post-dating the 1979 catalogue. (4) Landscape-Method Compatibility Proposition — introduced as theoretical justification: optimisation methods are effective only when their update operators align with the landscape's structural properties; (problem, method) space admits a natural compatibility partition; accompanied by three canonical mismatch examples (gradient descent on 3-SAT at phase transition, CDCL on continuous optimisation, generic GA on Dominating Set without decomposition) demonstrating that structural incompatibility cannot be remedied by parameter tuning. (5) Three universal quantitative indicators — Ruggedness R (neighbour objective autocorrelation), Constraint Propagation Density Dc (domain reduction ratio after variable fixing), and Gradient Smoothness Sg (Lipschitz constant of relaxation gradient) — with expected ranges tabulated per Box, converting classification from expert judgement into reproducible measurement. Overall effect: framework upgraded from descriptive taxonomy to formally grounded classification system with decidable indicators, theoretical justification, and empirical validation across classical and modern problems. Version 7 consolidates the framework's formal and statistical foundations along six dimensions: (i) The Landscape-Method Compatibility Proposition is accompanied by a working definition of "structural morphism" (neighbourhood preservation and basin preservation) and an explicit Status remark acknowledging its standing as a structural principle with empirical support rather than a formally proven theorem. (ii) The Adequacy Score is redefined as an explicit piecewise step function of problem scale and difficulty rather than an unspecified f (N × D). (iii) Surrogate uncertainty propagation is formalised via inverse-variance weighting, giving an explicit aggregation formula and standard-error expression for Gaussian-Process-backed difficulty scores. (iv) The multiple-testing correction section explicitly addresses score correlation, contrasting Bonferroni with Holm–Bonferroni and Benjamini–Hochberg alternatives for positive dependence. (v) The inapproximability citation for Dominating Set is corrected to the Feige (1998) Set-Cover reduction as primary source, with Dinur–Steurer (2014) retained as tightness reinforcement. (vi) The two separate speedup figures reported for Box 6—MCCO's 24, 000× algorithmic speedup and the reconnaissance-guided 3. 56× deployment speedup—are now explicitly disambiguated to prevent baseline confusion. Version 7 also adds an honest limitation concerning the operational definition of the ruggedness indicator R: preliminary calibration experiments suggest that naive lag-1 autocorrelation has limited discriminating power across Box types, and candidate refinements are listed for future work. Keywords: NP-hard, loss land