3 citations · 4 across the 3 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
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…
cs.CC2023★ 1 cited
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…