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 & Johnson 1979, FLA/ELA, Algorithm Selection, No Free Lunch, Parameterized Complexity, Learning-Augmented); 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 & Beasley (1998) reference added. Box 2a Graph Coloring: 50–200 nodes, density 0.1–0.5, framework saves 14–30% colors via DSatur + Tabu Search. Box 3a 3-SAT: tested across phase transition (α = 2.0–5.0), framework selects CDCL for hard instances, solves instances that blind WalkSAT cannot, 15.1× speedup at α = 4.2. Box 4b VRP: 20–100 customers, framework serves +44 additional customers (coverage 56% → 100%), natural application of cutting mechanism. Box 5a Scheduling: 20–200 jobs, framework wins by 7–27%, 200-job instance within 0.1% of lower bound. How Close to P cross-box comparison table: five of eight test cases at or near P, three within 1–2 orders of magnitude, zero large gaps. Improvement acceleration data: 9% at 20 cities → 66% at 50 cities → 80% at 100 cities. Conclusion upgraded: three-layer → four-layer acceleration (reconnaissance × transformation × cutting × AI execution); TSPLIB scaling evidence added. References: 16 → 18 (added Reinelt 1991 TSPLIB, Chu & Beasley 1998 MKP). v5 (2026-04-13): Unified error architecture across three layers: New Remark in Section 8.3 (Difficulty Scoring): formally establishes that transformation and cutting are deterministic functions of reconnaissance scores, introducing no independent statistical error. All inference risk is concentrated in the reconnaissance layer. Reconnaissance is inference; 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 & Macready (1997). Reference count: 18 → 16 (net −2 duplicates removed). Page count: 48 → 49 (+1 page of new statistical framework content, on the original v4 .tex source without content loss). v6 update: Comprehensive strengthening of the framework along five dimensions. (1) Literature support — every best-fit solver recommendation in every sub-box now has explicit citations (Martello & Toth 1990 for Knapsack, Applegate et al. 2006 for TSP, Nemhauser & Trotter 1975 for Vertex Cover, Chvátal 1979 for Set Cover, Dinur & Steurer 2014 for Dominating Set hardness, and 20+ others). (2) Sub-box boundary refinement — Set Cover removed from Box 1a; 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 & Johnson (1979)"; 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 D_c (domain reduction ratio after variable fixing), and Gradient Smoothness S_g (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.