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

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.

Mechanizing Gödel's Incompleteness Theorems and Provability Logic
Shogo Saitou, Mashu Noguchi
arXiv15 Sep 2026PreprintCC BY-SA 4.0Full textLogic & foundationsarXiv
Completeness of the Gödel--Löb Provability Logic for Finite Derived Ordinal Topologies
Mohammad Golshani
arXiv1 Sep 2026PreprintarXiv licenceFull textLogic & foundationsarXiv
n-Valued Analogue of Abel's Theorem
Mikhail Kornev
arXiv3 Oct 2026PreprintCC BY 4.0Full textAlgebra & number theoryarXiv
C⁰-Analogue of Ismagilov's Theorem
Stéphane Tchuiaga
arXiv20 Sep 2026PreprintCC BY 4.0Full textGeometry & topologyarXiv
A Group Analogue of the Ghurye--Olkin--Ibragimov Theorem
Gennadiy Feldman
arXiv16 Sep 2026PreprintarXiv licenceFull textProbabilityarXiv

Cite

BibTeX RIS

BibTeX

@misc{fang2026selfreferential,
  title = {{Self-Referential $K$-SAT and the Finite Analogue of Gödel's Incompleteness Theorem}},
  author = {Wen Fang and Xianxian Li and Jun Liu and Jie Luo and Yongxin Tong and Ke Xu},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2607.01671},
  eprint = {2607.01671},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2607.01671},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Self-Referential K-SAT and the Finite Analogue of Gödel's Incompleteness Theorem
AU  - Wen Fang
AU  - Xianxian Li
AU  - Jun Liu
AU  - Jie Luo
AU  - Yongxin Tong
AU  - Ke Xu
PY  - 2026
DA  - 2026/10/29
PB  - arXiv
DO  - 10.48550/arxiv.2607.01671
UR  - https://arxiv.org/abs/2607.01671
AB  - 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.
ER  -

Abstract

Related

Cite