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

Wen Fang, Xianxian Li, Jun Liu +3

Self-reference and solution independence are core properties underlying intractability. This paper establishes a finite combinatorial analogue of Gödel's incompleteness theorems w…