A Geometric Explanation of Computational Hardness

Read full text
Authors: DURGHAM QARALLEH
Cited by: 0

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