From P =? NP to Practice: Description Complexity and Certificate-First Automated Discovery of Approximation Algorithms and Heuristics for Hard Problems
Preprint
- 24 September 2025
- preprint
- Published by MDPI AG in Preprints.org
Abstract
We revisit the P ? = NP question through the joint lenses of time–relative description complexity and automated discovery. Our premise is epistemic rather than ontological: even if polynomial–time algorithms for NP–complete problems exist, they may have very high Kolmogorov (description) complexity and thus be undiscoverable by unaided humans. Formal barriers (relativization, natural proofs, and algebrization) already suggest that familiar techniques are insufficient to separate or collapse P and NP. Regardless of the ultimate truth of P ? = NP, we argue that systematic search in high–K code spaces is valuable today: it may yield stronger heuristics, tighter exponential bases, improved approximation schemes, and fixed–parameter runtimes. To make such artifacts scientifically credible, we advocate a certificate–first workflow ([9,78]) that couples (i) polytime–by–construction skeletons with (ii) machine–checkable evidence (e.g., DRAT/FRAT logs; LP/SDP duals) and (iii) non–uniform search distilled into uniform algorithms. We also note empirical motivation from large language models: scaling laws and energy budgets indicate that high capacity often unlocks new emergent behaviors, while internal mappings remain complex and opaque. The overarching message is pragmatic: capacity (high descriptive complexity) plus certification may provide a principled path to better algorithms and clearer limits without presuming a resolution of P ? = NP. This paper is best described as an position/expository essay. We synthesize existing work from complexity theory, Kolmogorov complexity, and algorithmic discovery, and offers a rational justification for a shift in emphasis: from the elusive goal of discovering polynomial-time algorithms for NP-complete problems, to the tractable and fruitful pursuit of discovering high-performance heuristics and approximation methods via automated search and learning.Keywords
All Related Versions
This publication has 46 references indexed in Scilit:
- Computational Complexity2024
- Equal numbers of neuronal and nonneuronal cells make the human brain an isometrically scaled‐up primate brainJournal of Comparative Neurology, 2009
- A tight bound on approximating arbitrary metrics by tree metricsJournal of Computer and System Sciences, 2004
- On the Complexity of k-SATJournal of Computer and System Sciences, 2001
- Computing with MembranesJournal of Computer and System Sciences, 2000
- Efficient Theoretic and Practical Algorithms for Linear Matroid Intersection ProblemsJournal of Computer and System Sciences, 1996
- A new recursion-theoretic characterization of the polytime functionscomputational complexity, 1992
- A Local-Ratio Theorem for Approximating the Weighted Vertex Cover Problem1985
- The ellipsoid method and its consequences in combinatorial optimizationCombinatorica, 1981
- The Theory ofp-nJunctions in Semiconductors andp-nJunction TransistorsBell System Technical Journal, 1949