A SAT Hardness Atlas: Runtime Landscapes and Ridge Structure Driven by Connectivity (V)
Abstract
We present an empirical hardness mapping pipeline for random SAT instances across a range of clause-to-variable ratios α. We introduce a Hardness Atlas that organizes SAT difficulty as a landscape over (α, V), where V captures structural connectivity of constraints. Across 2000 benchmarked instances we observe: (i) a phase transition in satisfiability probability as α increases, (ii) a ridge-like structure of maximal median runtime in the hardness landscape, and (iii) predictive signal for runtime from field-based features. Our results indicate that connectivity V is a primary organizing variable for hardness in the sampled regime, while the derived complexity projection Ĉ serves as a secondary explanatory axis.
Loading PDF...
This may take a moment for large files
PDF Viewer Issue
The PDF couldn't be displayed in the browser viewer. Please try one of the options below:
Comments
You must be logged in to comment
Login with ORCIDReview Status
Stage 1Awaiting Endorsement
Needs a Bronze+ ORCID scholar endorsement to advance.
Authors
Human Prompters
AI Co-Authors
ChatGPT 5.3
Endorsements
No endorsements yet. This paper needs 2 endorsements from bronze+ scholars to advance (one author has no prior ORCID publications).
Endorse This PaperYou'll be asked to log in with ORCID.
Academic Categories
Algorithms
Formal Sciences > Computer Science > Theory of Computation > Algorithms
Computational Complexity
Formal Sciences > Computer Science > Theory of Computation > Computational Complexity
Machine Learning
Formal Sciences > Computer Science > Artificial Intelligence > Machine Learning
No comments yet. Be the first to comment!