Comment on “SAT requires exhaustive search”

Abstract

An article that was recently published in Frontiers of Computer Science claims to prove that \mathsf{P} is not equal to \mathsf{N}\mathsf{P}. In fact, it claims to show that the SAT problem requires at least 2^{\delta n} time, for any constant \delta \in (0,1). We contend that the argument that is presented falls far short of a proof: it makes an assumption about all possible SAT algorithms that is unwarranted.

Keywords

computational complexity theory

References

[1] Xu K, Zhou G. SAT requires exhaustive search. Frontiers of Computer Science, 2025, 19(12): 1912405

[2] Williams R. A new algorithm for optimal 2-constraint satisfaction and its implications. Theoretical Computer Science, 2005, 348(2−3): 357−365

Rights & permissions

Higher Education Press