1 citations · 1 across the 4 of their papers we have counts for
4 papers
Self-Referential -SAT and the Finite Analogue of Gödel's Incompleteness Theorem
Wen Fang, Xianxian Li, Jun Liu +3
We study self-reference and solution independence in Boolean -SAT as a finite analogue of Gödel incompleteness. Independence is defined through factorial moments of the solution…
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.…
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…
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…