A Geometric Explanation of Computational Hardness
Abstract
We propose a geometric and trajectory-based explanation of computational hardness in NPproblems, centered around the concept of a structurally dense kernel. Through operationaldefinitions, predictive scaling experiments on random SAT instances, and a direct comparisonwith XOR-SAT, we demonstrate that exponential blow-up in search algorithms is consistentlypreceded by a measurable phenomenon we term kernel escape. Our results suggest that hardnessis not an intrinsic computational property, but rather a geometric instability arising from loss oftrajectory coherence. This framework offers a unifying interpretation of empirical solver behaviorand introduces a new perspective on algorithmic failure in complex combinatorial systems.
Fields of Study & Subjects
Constraint Satisfaction and Optimization
Advanced Graph Theory Research
Complexity and Algorithms in Graphs
Publication details
- Journal / source
- Figshare
- Publication date
- 27 February 2026
- Language
- EN
- Document type
- Thesis