A Critique of Du's "A Polynomial-Time Algorithm for 3-SAT
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909162306273280 |
|---|---|
| author | He, Yumeng Kotler-Berkowitz, Matan Liuson, Harry Nie, Zeyu |
| author_facet | He, Yumeng Kotler-Berkowitz, Matan Liuson, Harry Nie, Zeyu |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_04395 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Critique of Du's "A Polynomial-Time Algorithm for 3-SAT He, Yumeng Kotler-Berkowitz, Matan Liuson, Harry Nie, Zeyu Computational Complexity 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. |
| title | A Critique of Du's "A Polynomial-Time Algorithm for 3-SAT |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2404.04395 |