Self-Referential K-SAT and the Finite Analogue of Gödel’s Incompleteness Theorem

Jul 16, 2026

Upload by Violet

Self-reference and solution independence are core structural properties driving hard combinatorial instances. This paper studies whether Boolean K-SAT can exhibit both simultaneously, yielding a finite combinatorial analogue of Gödel’s incompleteness. For constant-width random K-SAT, overlapping assignments destroy independence. A new logarithmic-width ensemble (K=O(log N)) restores Poisson satisfying-count behavior, giving SAT/UNSAT coexistence near the critical scale. Single-clause substitution conditioned on the unique solution produces locally indistinguishable irreducible pairs and establishes unconditional local–global computational lower bounds with wide clauses forcing exponential proof blowup.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages33

Reading Time1 h 23 min

AccessFree to download

Introduction

Preliminaries

Boolean CNF

Solution Independence

Self-Reference

Random K-SAT Ensemble

Native Constant-Width Clauses

Logarithmic-Width CNF

Poisson Solution Counting and Projection Defect Bounds

Self-Referential SAT/UNSAT Flips

Structural Irreducibility Theorem

Finite Analogues of Gödel Incompleteness

Analogue of Gödel’s First Incompleteness Theorem

Analogue of Gödel’s Second Incompleteness Theorem

From Logical Necessity to Lower Bounds

Meta-Obstacles of Complexity Theory

From Structural Irreducibility to Descriptive Complexity

From Descriptive Complexity to Proof Complexity

Quantum Invariance of Structural Irreducibility

Discussion

Class Separation vs. Instance Indistinguishability

SETH is a Projection of Gödel Incompleteness

The Limits of Machine Learning

Conclusion

arXiv :2607 .0 167 1v 1 [ cs .CC] 2 Jul 2026 Self-Referential K-SAT and the Finite Analogue of G¨odel’s Incompleteness Theorem Wen Fang 1 , Xianxian Li2 , Jun Liu3 , Jie Luo 1 , Yongxin Tong 1 , Ke Xu 1∗ 1 State Key Lab of Complex and Critical Software Environment, Beihang University, Beijing, 100083, China 2 School of Computer Science and Engineering, Guangxi Normal University, Guilin, 541004, China 3 School of Mathematics, Taiyuan University of Technology, Taiyuan, 030600, China Abstract Self-reference and solution independence are core structural properties underlying hard combinatorial instances. This paper investigates whether Boolean K-SAT problems can simultaneously manifest both structural attributes, thereby establishing a precise, finite combinatorial analogue of G¨odel’s incompleteness theorems. For standard random K-SAT with a constant clause size, we demonstrate that strong correlations among highly overlapping assignments inevitably disrupt solution independence. To resolve this structural constraint, we introduce a novel random ensemble wherein the clause width scales logarithmically with the number of variables (K = O (log N)) . In this regime, the total satisfying assignment count converges to a standard Poisson distribution, enabling unsatisfiable and uniquely satisfiable formulas to coexist with positive limiting probabilities at the critical scale. By executing a single-clause substitution conditioned on the unique solution, we construct structurally irreducible SAT/UNSAT pairs that are indistinguishable via local evaluation. Mirroring G¨odel’s unprovable sentence, this construction deploys the formula’s own unique solution to invert global satisfiability. To elucidate the computational hardness induced by this local-global asymmetry, we analyze the structural limits of algorithmic compression. Utilizing algorithmic information theory and Shannon entropy channels, we prove that any deterministic deductive pipeline restricted to a sublinear window suffers from an inescapable informational blind spot, forcing a strict descriptive lower bound on the algorithm (K(A) ≥ Ω(N1−δ )) . This localized information deficit acts as an unconditional barrier for formal reasoning, forcing any valid Resolution refutation of the unsatisfiable instance to utilize exceptionally wide clauses (w(π) ≥ Ω(N1−δ )), which inevitably triggers an exponential explosion in proof-tree size (S(ϕ) ≥ exp(Ω(N1−2δ ))) . Pushing this structural isolation parameter to its theoretical limit (δ → 0+ ) yields a smooth mathematical convergence with the worst-case 2N search threshold. This alignment demonstrates that runtime boundaries are strictly dictated by static information conservation laws, reframing the Strong Exponential Time Hypothesis (SETH) as a direct projection of G¨odel incompleteness onto finite physical computing systems. This work diagnoses the decades-long stagnation in complexity theory. We reveal that the fundamental barrier is a binary logical necessity, not an algorithmic failure. By transitioning from Turing’s abstract class separation to a G¨odelian paradigm of instance indistinguishability, we introduce a multi-dimensional comparative framework that systematically contrasts these two historical lineages across distinct analytical perspectives. Finally, we demonstrate the physical invariance of the self-referential hardness across changing computing paradigms: it precludes any quantum algorithmic shortcut due to the absolute necessity of global semantic analysis, and it delineates a fundamental scaling bottleneck for modern machine learning architectures that operate purely on lossy, local statistical compression. Keywords: K-SAT; solution independence; self-reference; G¨odel incompleteness; structural irreducibility; logical necessity; descriptive complexity; Poisson distribution; SETH. Contents 1 Introduction 3 2 Preliminaries 5 2.1 Boolean CNF ................................... 5 2.2 Solutio

FAQs

What structural properties does the paper focus on for hard combinatorial instances?

It focuses on self-reference and solution independence, treating them as core structural attributes that shape the hardness of combinatorial problems.

Why do constant-width random K-SAT instances fail to maintain solution independence?

In the constant clause-size regime, strong correlations among highly overlapping assignments inevitably disrupt solution independence.

How does the logarithmic-width ensemble enable a finite analogue of Gödel-type incompleteness?

By letting clause width scale logarithmically (K=O(log N)), the number of satisfying assignments converges to a Poisson distribution, allowing SAT and UNSAT with positive limiting probabilities at the critical scale, while a conditional substitution construction creates locally indistinguishable irreducible SAT/UNSAT pairs.

Jul 16, 2026

Upload by Violet