Comment on “SAT requires exhaustive search”

Adv search

Comment on “SAT requires exhaustive search”

Eric ALLENDER , Ryan WILLIAMS

Front. Comput. Sci. ›› 2026, Vol. 20 ›› Issue (1) : 2001405

PDF (122KB)

Front. Comput. Sci. ›› 2026, Vol. 20 ›› Issue (1) : 2001405 DOI: 10.1007/s11704-025-53000-5

CORRESPONDENCE

Comment on “SAT requires exhaustive search”

Eric ALLENDER ¹^,^‡
, Ryan WILLIAMS ²^,^‡

Author information +

History +

PDF (122KB)

Abstract

An article that was recently published in Frontiers of Computer Science claims to prove that $P$ is not equal to $N P$ . In fact, it claims to show that the SAT problem requires at least $2 δ n$ time, for any constant $δ ∈ (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

Cite this article

Download citation ▾

Eric ALLENDER, Ryan WILLIAMS. Comment on “SAT requires exhaustive search”. Front. Comput. Sci., 2026, 20(1): 2001405 DOI:10.1007/s11704-025-53000-5

登录浏览全文

4963

注册一个新账户忘记密码

References

Publishing order | Descend order by publishing year | Descend order by cited within

[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

AI Summary AI Mindmap

PDF (122KB)

225

Accesses

0

Citation

Detail

Sections

Recommended

/

〈

〉