PulseExploreJournal ClubDebatesTrendingResearchersJournals
Instagram
HomeExploreJournal ClubTrending
Synapse
⌘+K
Synapse
February 8, 20260 citationsOpen Access

Finding the Path Home: A Geometric Exploration of P = NP

View Full Paper
CACiarán AsherKAKimberley AsherAAAneska Asher

Key Points

  • This research aims to explore a geometric approach to the P = NP problem by developing a new descent algorithm that mitigates cross-clause interference.
  • Introduced a potential function for clause-local decomposition.
  • Developed a harmonic neighbourhood descent operator to compute multi-variable corrections.
  • Implemented a recursive cascade correction with adaptive decay.
  • Achieved a guaranteed global potential decrease at each algorithmic step.
  • Established a polynomial runtime for both satisfiable and unsatisfiable formulas.
  • Showed that the algorithm can extract a minimal unsatisfiable subset when faced with unsatisfiability.

Abstract

This paper introduces a mechanism that directly addresses cross-clause interference through a multi-scale descent process with three components: (i) A potential function with clause-local decomposition. We define a rational-valued potential Φ(s) = U(s) + F(s)/B over 3-SAT states, where U counts unsatisfied clauses, F is a clause-local tie-breaking term with distinct weights, and B = n⁴ is a scale constant. This potential is zero if and only if the current assignment satisfies the formula, has polynomial range, and is computable in polynomial time with O(log n)-bit arithmetic. (ii) A harmonic neighbourhood descent operator. Rather than flipping a single variable, the algorithm computes a gradient-directed multi-variable correction within the coupled neighbourhood of the first unsatisfied clause. This multi-flip has visibility into the cross-clause coupling structure and can coordinate corrections that a single-flip operator cannot. (iii) A recursive cascade correction with adaptive decay. The neighbourhood descent may perturb clauses beyond its immediate scope. To manage this, the algorithm deploys a self-replicating cascade of progressively smaller corrections. At each cascade level, the actual perturbation arriving at boundary clauses is measured and a calibrated correction is applied. The cascade terminates in O(log n) levels, and the total correction work is polynomial. The net global potential decrease is a provable constant fraction of the initial local improvement. Together, these components form a composite descent operator that guarantees strict global potential decrease of at least 1/(2B) at every step. Since the potential has range at most m + 1, the algorithm terminates after at most O(m · n⁴) accepted descents, each requiring polynomial work. The total runtime is polynomial in the size of the input formula. When the formula is satisfiable, the algorithm terminates with a satisfying assignment. When the formula is unsatisfiable, a terminal plateau triggers extraction of a contradictory core — a minimal unsatisfiable subset of clauses with a polynomial-time verifiable refutation.

Ask AI
Helpful
Bookmark
Share
View Full Paper

Cite This Study

Asher et al. (2026) studied this question.

synapsesocial.com/papers/698828cb0fc35cd7a884898bhttps://doi.org/10.5281/zenodo.18509022
Ask AI
Helpful
Bookmark
Share
View Full Paper