A Critique of Chen's "The 2-MAXSAT Problem Can Be Solved in Polynomial Time"
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909155449634816 |
|---|---|
| author | Le, Tran Duy Anh Reidy, Michael P. Smith, Eliot J. |
| author_facet | Le, Tran Duy Anh Reidy, Michael P. Smith, Eliot J. |
| contents | In this paper, we examine Yangjun Chen's technical report titled ``The 2-MAXSAT Problem Can Be Solved in Polynomial Time'' [Che23], which revises and expands upon their conference paper of the same name [Che22]. Chen's paper purports to build a polynomial-time algorithm for the ${\rm NP}$-complete problem 2-MAXSAT by converting a 2-CNF formula into a graph that is then searched. We show through multiple counterexamples that Chen's proposed algorithms contain flaws, and we find that the structures they create lack properly formalized definitions. Furthermore, we elaborate on how the author fails to prove the correctness of their algorithms and how they make overgeneralizations in their time analysis of their proposed solution. Due to these issues, we conclude that Chen's technical report [Che23] and conference paper [Che22] both fail to provide a proof that ${\rm P}={\rm NP}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_00006 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Critique of Chen's "The 2-MAXSAT Problem Can Be Solved in Polynomial Time" Le, Tran Duy Anh Reidy, Michael P. Smith, Eliot J. Computational Complexity In this paper, we examine Yangjun Chen's technical report titled ``The 2-MAXSAT Problem Can Be Solved in Polynomial Time'' [Che23], which revises and expands upon their conference paper of the same name [Che22]. Chen's paper purports to build a polynomial-time algorithm for the ${\rm NP}$-complete problem 2-MAXSAT by converting a 2-CNF formula into a graph that is then searched. We show through multiple counterexamples that Chen's proposed algorithms contain flaws, and we find that the structures they create lack properly formalized definitions. Furthermore, we elaborate on how the author fails to prove the correctness of their algorithms and how they make overgeneralizations in their time analysis of their proposed solution. Due to these issues, we conclude that Chen's technical report [Che23] and conference paper [Che22] both fail to provide a proof that ${\rm P}={\rm NP}$. |
| title | A Critique of Chen's "The 2-MAXSAT Problem Can Be Solved in Polynomial Time" |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2404.00006 |