Logo image
Comment on "SAT Requires Exhaustive Search"
Journal article   Peer reviewed

Comment on "SAT Requires Exhaustive Search"

Eric Allender and Ryan Williams
Vol.20(1)
09/17/2025

Abstract

Computational complexity

An article that was recently published in Frontiers of Computer Science claims to prove that P is not equal to NP. 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.

pdf
allender.williams218.02 kB
Accepted Manuscript (AM) Frontiers of Computer Science Embargoed Access, Embargo ends: 09/17/2026, To request access, contact soarhelp@libraries.rutgers.edu.
url
https://doi.org/10.1007/s11704-025-53000-5View
Version of Record (VoR) Frontiers of Computer Science
url
Report an accessibility issueView
Please complete a content remediation request to report an accessibility issue with a library electronic resource, website, or service.

Metrics

17 Record Views

Details

Logo image