A Critique of Du's "A Polynomial-Time Algorithm for 3-SAT
<|reference_start|>A Critique of Du's "A Polynomial-Time Algorithm for 3-SAT: In this paper, we examine the claims made by the paper "A polynomial-time algorithm for 3-SAT" by Lizhi Du. The paper claims to provide a polynomial-time algorithm for solving the NP-complete problem 3-SAT. In examining the paper's argument, we find a flaw in one of the main sections of its algorithm. We argue that this flaw causes the paper's algorithm to incorrectly decide that an infinite family of satisfiable 3-CNF boolean formulas are not satisfiable. Therefore, the paper does not establish that P = NP.<|reference_end|>
@article{he2024a,
    title={A Critique of Du's "A Polynomial-Time Algorithm for 3-SAT},
    author={Yumeng He, Matan Kotler-Berkowitz, Harry Liuson, Zeyu Nie},
    journal={arXiv preprint arXiv:2404.04395},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.04395},
    primaryClass={cs.CC}
}