{"ID":5675113,"CreatedAt":"2026-07-03T01:40:09.565152011Z","UpdatedAt":"2026-07-05T03:52:30.756976999Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.01671","arxiv_id":"2607.01671","title":"Self-Referential $K$-SAT and the Finite Analogue of Gödel's Incompleteness Theorem","abstract":"Self-reference and solution independence are core properties underlying intractability. This paper establishes a finite combinatorial analogue of Gödel'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 Ω(N^{1-δ})$. This deficit forces any Resolution refutation of the UNSAT instance to utilize wide clauses ($w(π) \\geq Ω(N^{1-δ})$), triggering an exponential proof-tree explosion ($S(φ) \\geq \\exp(Ω(N^{1-2δ}))$). As $δ\\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ödel incompleteness onto finite computation. We diagnose the decades-long stagnation in complexity theory. Transitioning from Turing's class separation to a Gödelian 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.","short_abstract":"Self-reference and solution independence are core properties underlying intractability. This paper establishes a finite combinatorial analogue of Gödel's incompleteness theorems within Boolean $K$-SAT. While standard random $K$-SAT has assignment correlations that disrupt solution independence, we resolve this via a lo...","url_abs":"https://arxiv.org/abs/2607.01671","url_pdf":"https://arxiv.org/pdf/2607.01671v1","authors":"[\"Wen Fang\",\"Xianxian Li\",\"Jun Liu\",\"Jie Luo\",\"Yongxin Tong\",\"Ke Xu\"]","published":"2026-07-02T03:52:23Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.DS\",\"cs.IT\",\"cs.LO\"]","methods":"[]","has_code":false}