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 w…
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
SAT Requires Exhaustive Search
Ke Xu, Guangyan Zhou
In this paper, by constructing extremely hard examples of CSP (with large domains) and SAT (with long clauses), we prove that such examples cannot be solved without exhaustive sear…