A Landscape Classification Framework for NP-Hard Problems: From Reconnaissance to Algorithm Selection
Fuente:
Zenodo
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Recurso digital |
| Lenguaje: | inglés |
| Publicado: |
Zenodo
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866901878137159680 |
|---|---|
| author | Rao, Huiying |
| author_facet | Rao, Huiying |
| contents | <p>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.</p> <p class="font-claude-response-body break-words whitespace-normal leading-[1.7]"><strong>v2 (2026-04-11):</strong> 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.</p> <p><strong>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.</strong></p> |
| format | Recurso digital |
| id | zenodo_https___doi_org_10_5281_zenodo_19513729 |
| institution | Zenodo |
| language | eng |
| publishDate | 2026 |
| publisher | Zenodo |
| record_format | zenodo |
| spellingShingle | A Landscape Classification Framework for NP-Hard Problems: From Reconnaissance to Algorithm Selection Rao, Huiying NP-hard loss landscape algorithm selection fitness landscape analysis combinatorial optimisation meta-algorithm landscape classification reconnaissance MCCO <p>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.</p> <p class="font-claude-response-body break-words whitespace-normal leading-[1.7]"><strong>v2 (2026-04-11):</strong> 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.</p> <p><strong>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.</strong></p> |
| title | A Landscape Classification Framework for NP-Hard Problems: From Reconnaissance to Algorithm Selection |
| topic | NP-hard loss landscape algorithm selection fitness landscape analysis combinatorial optimisation meta-algorithm landscape classification reconnaissance MCCO |
| url | https://doi.org/10.5281/zenodo.19513729 |