الأوربوروس المنطقي: عندما ينكر K-SAT نفسه ✛ ✦

الملخص الأصلي

كما كتبه المؤلفون، بالإنجليزية arXiv:2607.01671

Self-reference and solution independence are core properties underlying intractability. This paper establishes a finite combinatorial analogue of G\"odel's incompleteness theorems within Boolean $$K$$-SAT. While standard random $$K$$-SAT has assignment correlations that disrupt solution independence, we resolve this via a logarithmic-width ensemble ($$K = O(\log N)$$). Here, satisfying assignments converge to a Poisson distribution, letting unsatisfiable and uniquely satisfiable formulas coexist. By executing a single-clause substitution conditioned on the unique solution, we construct structurally irreducible SAT/UNSAT pairs that are indistinguishable via local evaluation. Using algorithmic information theory and Shannon channels, we prove that deductive pipelines restricted to a sublinear window suffer from an informational blind spot, forcing a descriptive lower bound of $$K(\mathcal{A}) \geq \Omega(N^{1-\delta})$$. This deficit forces any Resolution refutation of the UNSAT instance to utilize wide clauses ($$w(\pi) \geq \Omega(N^{1-\delta})$$), triggering an exponential proof-tree explosion ($$S(\phi) \geq \exp(\Omega(N^{1-2\delta}))$$). As $$\delta \rightarrow 0^+$$, this bound converges to the worst-case $$2^N$$ threshold, reframing the Strong Exponential Time Hypothesis (SETH) as a direct projection of G\"odel incompleteness onto finite computation. We diagnose the decades-long stagnation in complexity theory. Transitioning from Turing's class separation to a G\"odelian paradigm of instance indistinguishability, we introduce a multi-dimensional comparative framework that contrasts these two historical lineages across distinct perspectives. The self-referential hardness exhibits physical invariance: it precludes quantum shortcuts due to the necessity of global semantic analysis and delineates a scaling bottleneck for machine learning architectures operating on lossy, local compression.