Self-Referential K-SAT and the Finite Analogue of G"odel's Incompleteness Theorem

arXiv:2607.01671 · cs.CC, cs.DS, cs.IT, cs.LO, math.IT · Submitted 2026-07-02 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Self-Referential K-SAT and the Finite Analogue of G"odel's Incompleteness Theorem".

Jane: Here's the gist of the paper. Self-reference and solution independence are core properties of hard combinatorial instances <ref:2607.01671#pg3> The paper asks whether Boolean K-SAT can manifest both, establishing a finite combinatorial analogue of Gödels incompleteness theorems <ref:2607.01671#pg4>.

Tom: Defining Solution Independence The authors formalize solution independence using factorial moments of the satisfying-assignment count <ref:2607.01671#pg5> They define the weakest form as the critical second-moment condition, where E

X: → λ and E

X(X − 1): /E

X: 2 → 1 <ref:2607.01671#pg6>.

Jane: A stronger sufficient condition is factorial-moment convergence, implying X ⇒ Poisson(λ) <ref:2607.01671#pg6>.

Tom: The Poisson form is noted as the cleanest way to express the coexistence of unsatisfiable and uniquely satisfiable instances with positive limiting probability <ref:2607.01671#pg6>.

Paper summary: Jane: The authors formalize solution independence using factorial moments of the satisfying assignment count Jane They define a weak form by saying that if EX goes to lambda and E

X(X minus one): over EX squared goes to one, that's the critical second-moment condition Jane <ref:2607.01671#pg1,factorial moments of the satisfying assignment count>

Tom: That second moment condition is essentially checking if the number of solutions is behaving like a Poisson variable, which means we’re looking at how hard it is to find those assignments Tom But they say that stronger conditions exist, specifically factorial-moment convergence implying X implies a Poisson distribution Tom

Lu: And then they use this idea in their setup. They introduce a random CNF ensemble with logarithmic clause width K equals O(log N) at the subcube-covering threshold M equals theta of N2 plus epsilon Lu This specific regime is what lets them get that Poisson behavior we mentioned earlier Lu

Meng: And they then use this to create a SAT and UNSAT pair that has the same unsigned clause–variable incidence graph, which is a really neat construction for creating these linked instances Meng It’s about making sure the structure of the problems mirrors each other exactly so you can study them together Meng

Tom: So, what they claim is that this setup allows unsatisfiable and uniquely satisfiable formulas to coexist with positive limiting probabilities Tom This feels like a finite version of something huge in logic Tom

Jane: Exactly. The authors prove a structural irreducibility theorem, meaning for any small local subinstance of size at most Nc with c fixed between zero and one, the unique satisfiable formula and its unsatisfiable companion have identical local views Jane

Lu: That structural irreducibility is the finite, propositional analogue of Gödel’s self-referential construction formulated within a local subinstance-evaluation model Lu It shows that if the local pieces are too small, they can't tell the global story without looking at everything Lu

Tom: So what does this mean for the world? Tom

Conclusion: Jane: So looking at the title, "Self-Referential K-SAT and the Finite Analogue of G 00f6del's Incompleteness Theorem," it’s clear they are linking hard combinatorial problems to deep logical impossibility results Jane It’s about showing that these limitations exist even in this finite world of Boolean SAT Jane

Tom: The authors, Wen Fang, Xianxian Li, Jun Liu, Jie Luo, Yongxin Tong, and Ke Xu at State Key Lab of Complex and Critical Software Environment at Beihang University and Guangxi Normal University are working on encoding this structure Tom It’s not just a theoretical curiosity; it’s about how deep these self-referential properties go in computation Tom

Lu: What they really contribute is showing that this kind of structural rigidity forces any solver to evaluate the entire instance to find the answer, which is a finite version of G 00f6del's idea about formal systems Lu This implies there are fundamental limits on what local methods can tell you about a global system Lu

Meng: From an engineering standpoint, this means that if you build a system relying only on looking at small chunks of the problem, it fundamentally won't be able to solve the whole thing reliably without some global knowledge Meng It sets a hard limit for purely local statistical learning architectures Meng

Tom: And they also connect this hardness to complexity theory. They show that the proof-size lower bounds across different proof systems are qualitatively consistent with what SETH suggests about exponential-time hardness Tom

Jane: That’s the connection—it suggests that SETH is just a finite projection of Gödel incompleteness onto resource-bounded computation Jane So, this isn't just about logic; it's a constraint on how efficiently we can compute things in general Jane

Wen Fang, Xianxian Li, Jun Liu, Jie Luo, Yongxin Tong, Ke Xu

State Key Lab of Complex and Critical Software Environment, Beihang University · School of Computer Science and Engineering, Guangxi Normal University · School of Mathematics, Taiyuan University of Technology

cs.CC, cs.DS, cs.IT, cs.LO, math.IT

Submitted: 2026-07-02

Updated: 2026-10-29

Comments: 44 pages; Section 7.2 added

Project page: https://rb-bench.github.io

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 89/100

The gist: Self-reference and solution independence are core properties of hard combinatorial instances <ref:2607.01671#pg3> The paper asks whether Boolean K-SAT can manifest both…

Key concepts

Solution Independence
This concept measures how reliably a problem has a unique solution. It is formalized using factorial moments of the count of satisfying assignments. The paper uses a critical second-moment condition to define the weakest form, showing how the probability of having exactly one solution relates to the average number of solutions.
Self-Referential Construction
This is a structural technique where a formula refers to its own properties within a local subinstance. The authors prove that for small local parts, this construction creates an identical view between the uniquely satisfiable and unsatisfiable versions of the problem, mirroring Gödel's self-referential logic.
Structural Irreducibility Theorem
This theorem establishes that for any small part of a formula, its uniquely satisfiable version and its unsatisfiable companion share the same local structure. This structural identity is key to showing that local deductions are blind to global semantic truths, forming a finite analogue of Gödel's incompleteness.
Self-Recognition Obstacle
This obstacle explains why purely localized syntactic deduction fails to capture global semantic reality. It suggests that classical barriers like relativization and natural proofs arise because local reasoning cannot directly access the overall truth or structure of the entire problem.

Terminology

Summary

Self-reference and solution independence are core properties of hard combinatorial instances <ref:2607. p. 0

Where the paper says it

Self-Referential K-SAT and the Finite Analogue of G¨odel’s Incompleteness Theorem Wen Fang1 , Xianxian Li2 , Jun Liu3 , Jie Luo1 , Yongxin Tong1 , Ke Xu1∗ 1State Key Lab of Complex and Critical Software Environment, Beihang University, Beijing, 100083, China 2School of Computer Science and Engineering, Guangxi Normal University, Guilin, 541004, China 3School of Mathematics, Taiyuan University of Technology, Taiyuan, 030600, China Abstract Self-reference and solution independence are core properties of hard combinatorial instances. We ask whether Boolean K-SAT can manifest both, establishing a finite combinatorial analogue of G¨odel’s incompleteness theorems.

01671#pg3> The paper asks whether Boolean K-SAT can manifest both, establishing a finite combinatorial analogue of Gödels incompleteness theorems <ref:2607. p. 0
Where the paper says it

Self-Referential K-SAT and the Finite Analogue of G¨odel’s Incompleteness Theorem Wen Fang1 , Xianxian Li2 , Jun Liu3 , Jie Luo1 , Yongxin Tong1 , Ke Xu1∗ 1State Key Lab of Complex and Critical Software Environment, Beihang University, Beijing, 100083, China 2School of Computer Science and Engineering, Guangxi Normal University, Guilin, 541004, China 3School of Mathematics, Taiyuan University of Technology, Taiyuan, 030600, China Abstract Self-reference and solution independence are core properties of hard combinatorial instances. We ask whether Boolean K-SAT can manifest both, establishing a finite combinatorial analogue of G¨odel’s incompleteness theorems.

01671#pg4>.

Defining Solution Independence

The authors formalize solution independence using factorial moments of the satisfying-assignment count <ref:2607.01671#pg5> They define the weakest form as the critical second-moment condition, where E[X] → λ and E[X(X − 1)]/E[X]2 → 1 <ref:2607. p. 5

Where the paper says it

2 Solution Independence For an assignment σ, define Iσ(F) = 1{σ satisfies F}. The weakest form of solution independence used here is the critical second-moment condition: E[X] → λ, 0 < λ < ∞, and E[X(X − 1)] E[X] 2 → 1.

01671#pg6>. A stronger sufficient condition is factorial-moment convergence, implying X ⇒ Poisson(λ) <ref:2607. p. 3
Where the paper says it

This characterizes the standard threshold condition and establishes a stronger Poisson asymptotic convergence. The weakest form used is the critical second-moment condition E[X] → λ and E[X(X − 1)]/E[X] 2 → 1; the strongest form is factorial-moment convergence implying X ⇒ Poisson(λ).

01671#pg6>. The Poisson form is noted as the cleanest way to express the coexistence of unsatisfiable and uniquely satisfiable instances with positive limiting probability <ref:2607. p. 5
Where the paper says it

In particular, P[X = 0] → e −λ , P[X = 1] → λe−λ . The Poisson form is the cleanest way to express the coexistence of unsatisfiable and uniquely satisfiable instances with positive limiting probability.

01671#pg6>.

How the training signal is built

The paper introduces a random CNF ensemble with logarithmic clause width K = O(log N) at a subcube-covering threshold M = Θ(N2 + ε) <ref:2607.01671#pg9>. In this regime, the total satisfying-assignment count converges to a Poisson distribution, enabling unsatisfiable and uniquely satisfiable formulas to coexist with positive limiting probabilities <ref:2607. p. 0

Where the paper says it

To overcome this obstruction, we introduce a random CNF ensemble with logarithmic clause width K = O(log N) at the subcube-covering threshold M = Θ(N2+ε ). In this regime the total satisfying-assignment count converges to a Poisson distribution, enabling unsatisfiable and uniquely satisfiable formulas to coexist with positive limiting probabilities.

01671#pg10>. They then perform a single-clause replacement using the unique solution to create a SAT/UNSAT pair with the same unsigned clause–variable incidence graph. p. 0
Where the paper says it

In this regime the total satisfying-assignment count converges to a Poisson distribution, enabling unsatisfiable and uniquely satisfiable formulas to coexist with positive limiting probabilities. Using one redundant clause and the unique solution, we perform a single-clause replacement whose new clause is falsified by that unique solution, producing a SAT/UNSAT pair with the same unsigned clause–variable incidence graph.

Where the gains come from

The authors prove a structural irreducibility theorem: for every local subinstance of size at most Nc with fixed 0 < c < 1, the uniquely satisfiable formula and its unsatisfiable companion have identical local views. This result is a finite, propositional analogue of Gödels self-referential construction formulated within a local subinstance-evaluation model. p. 0

Where the paper says it

Thus no deterministic or bounded-error clause-query evaluator restricted to that scale can distinguish unique satisfiability from unsatisfiability. This result is a finite, propositional analogue of G¨odel’s self-referential construction; it is formulated within a local subinstance-evaluation model and is not by itself a timecomplexity lower bound.

They also quantify the induced local–global information gap, showing that any transcript of t = N1−δ clause queries leaves N − o(N) bits of witness entropy. p. 0
Where the paper says it

We then quantify the induced local–global information gap. Any transcript of t = N1−δ clause queries leaves N −o(N) bits of witness entropy, so the global unique solution remains almost completely hidden from bounded local observation.

Proof-Complexity Lower Bounds

On typical support graphs satisfying a uniform expansion condition, the same self-referential construction yields linear Resolution width Ω(N) and hence exponential Resolution refutation size 2Ω(N). Similar bounds hold for Polynomial Calculus and PCR, SOS degree, bounded-product-width Positivstellensatz, and semantic Cutting Planes under explicit partition conditions. p. 4

Where the paper says it

The same expansion and pseudoexpectation arguments yield linear degree and exponential monomial size for Polynomial Calculus and PCR, linear SOS degree and exponential SOS monomial size, bounded-product-width Positivstellensatz lower bounds, and, under an explicit partition condition, exponential semantic Cutting Planes lower bounds. These bounds are preserved by the support-preserving self-referential flip and hold uniformly over all unsatisfiable signings on the same support graph, including companions chosen after observing the unique solution.

These lower bounds are preserved by the support-preserving self-referential flip. p. 4
Where the paper says it

The same expansion and pseudoexpectation arguments yield linear degree and exponential monomial size for Polynomial Calculus and PCR, linear SOS degree and exponential SOS monomial size, bounded-product-width Positivstellensatz lower bounds, and, under an explicit partition condition, exponential semantic Cutting Planes lower bounds. These bounds are preserved by the support-preserving self-referential flip and hold uniformly over all unsatisfiable signings on the same support graph, including companions chosen after observing the unique solution.

Link to SETH

The resulting 2Ω(N) proof-size lower bounds across different proof systems are qualitatively consistent with the exponential-time hardness posited by SETH, suggesting that SETH is a finite projection of Gödels incompleteness onto resource-bounded computation. The same self-referential hardness is invariant under quantum computing and delimits a fundamental scaling bottleneck for purely local statistical learning architectures. p. 1

Where the paper says it

bounds across different proof systems are qualitatively consistent with the exponentialtime hardness posited by SETH, suggesting that SETH is a finite projection of G¨odel incompleteness onto resource-bounded computation. The same self-referential hardness is invariant under quantum computing and delimits a fundamental scaling bottleneck for purely local statistical learning architectures.

Meta-Obstacles for Complexity Theory

The authors diagnose the long-standing stagnation in lower-bound theory through two structural constraints: the Self-Recognition Obstacle and the Static-Dynamic Obstacle. The first explains why localized syntactic deduction is structurally blind to global semantic truth and why classical barriers such as relativization, natural proofs, and algebrization arise. p. 4

Where the paper says it

• Meta-Obstacles for Complexity Theory: We diagnose the long-standing stagnation in lower-bound theory through two structural constraints: the Self-Recognition Obstacle and the Static-Dynamic Obstacle. The first explains why localized syntactic deduction is structurally blind to global semantic truth and why classical barriers such as relativization, natural proofs, and algebrization arise.

The second explains why purely static mathematical axioms cannot directly yield unconditional temporal lower bounds without a bridge to operational semantics. p. 4
Where the paper says it

The first explains why localized syntactic deduction is structurally blind to global semantic truth and why classical barriers such as relativization, natural proofs, and algebrization arise. The second explains why purely static mathematical axioms cannot directly yield unconditional temporal lower bounds without a bridge to operational semantics.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Structural Irreducibility for SAT Solvers: AI systems can be designed to operate only on local subinstances of a formula size Nc, ensuring that no deterministic or bounded-error clause-query evaluator restricted to that scale can distinguish unique satisfiability from unsatisfiability.

  2. Information Gap Quantification: The system can quantify the local–global information gap by observing that any transcript of t = N1−δ clause queries leaves N −o(N) bits of witness entropy, meaning local observation exposes only a vanishing fraction of the witness entropy required to recover the global unique solution.

  3. Proof System Hardness Bounds: The system can derive explicit proof size lower bounds across various deductive models, such as linear Resolution width, linear PC/PCR and SOS degree, and exponential proof size for unsatisfiable companions, based on the expansion properties of the unsigned incidence graph.

  4. Quantum Invariance for Hardness: The AI system's hardness assessment is invariant under quantum computing regimes because "any valid quantum algorithm tackling a self-referential instance is bounded by the same sublinear informational threshold and must evaluate global information, precluding any structural quantum shortcut from bypassing the instance’s total semantic analysis."

  5. Machine Learning Constraint: For deep learning architectures, the system dictates that models constrained to local information lack the programmatic representation and descriptive expressivity to encode the full configuration space of self-referential instances, implying a hard limit on their capacity for encoding complex combinatorial truths.

Abstract

We study self-reference and solution independence in Boolean K-SAT as a finite analogue of Gödel incompleteness. Independence is defined through factorial moments of the solution count. Constant-width random formulas fail this criterion due to correlations among overlapping assignments. At a covering threshold, logarithmic-width random CNFs have a Poisson solution count, with positive probabilities of unsatisfiability and unique satisfiability. Replacing a redundant clause by one falsified by the unique solution yields an unsatisfiable companion preserving the unsigned incidence graph. For every permitted local view of a good uniquely satisfiable formula, an unsatisfiable companion preserves that view. Irreducibility defeats deterministic and bounded-error evaluators using N c clause queries, for fixed 0<c<1. It establishes a local information obstruction, not an unrestricted time lower bound. For fixed δ>0, transcripts of N 1-δ queries leave N-o(N) bits of witness entropy. On typical support graphs, expansion yields linear Resolution width, linear PC/PCR and SOS degree, and exponential proof size. Bounds hold for semantic Cutting Planes under a partition condition and for Positivstellensatz with bounded product width, uniformly over unsatisfiable support-preserving signings. Structural evidence and the limits of acceleration strategies motivate the self-referential K-SAT exhaustive-search hypothesis (SRK-ESH): no uniform deterministic algorithm deciding the promise family achieves a fixed proportional saving in the exponent. This dual-evidence criterion combines intrinsic hardness mechanisms with algorithmic evidence. We interpret this hypothesis as a quantitative projection of the Gödel-style local--global gap. The information obstruction constrains quantum local observation and statistical learning from bounded local information.

Sources

Related papers