3 papers
cs.CC2026
Self-Referential -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 wi…
cs.CC2026
Solution independence and self-referential instances
Guangyan Zhou, Bin Wang, Jianxin Wang +1
In this paper, we investigate the hitting set problem and demonstrate that solution independence is the crucial property underlying the construction of self-referential instances.…
cs.CC2024
Further Explanations on "SAT Requires Exhaustive Search"
Qingxiu Dong, Guangyan Zhou, Ke Xu
Recently, Xu and Zhou [2023] introduced a constructive approach for exploring computational hardness, proving that SAT requires exhaustive search. In light of certain misinterpreta…