A Critique of Quigley's "A Polynomial Time Algorithm for 3SAT"
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918172775415808 |
|---|---|
| author | DeJesse, Nicholas Lyudovyk, Spencer Pai, Dhruv |
| author_facet | DeJesse, Nicholas Lyudovyk, Spencer Pai, Dhruv |
| contents | In this paper, we examine Quigley's "A Polynomial Time Algorithm for 3SAT" [Qui24]. Quigley claims to construct an algorithm that runs in polynomial time and determines whether a boolean formula in 3CNF form is satisfiable. Such a result would prove that 3SAT $\in \text{P}$ and thus $\text{P} = \text{NP}$. We show Quigley's argument is flawed by providing counterexamples to several lemmas he attempts to use to justify the correctness of his algorithm. We also provide an infinite class of 3CNF formulas that are unsatisfiable but are classified as satisfiable by Quigley's algorithm. In doing so, we prove that Quigley's algorithm fails on certain inputs, and thus his claim that $\text{P} = \text{NP}$ is not established by his paper. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_22985 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Critique of Quigley's "A Polynomial Time Algorithm for 3SAT" DeJesse, Nicholas Lyudovyk, Spencer Pai, Dhruv Computational Complexity In this paper, we examine Quigley's "A Polynomial Time Algorithm for 3SAT" [Qui24]. Quigley claims to construct an algorithm that runs in polynomial time and determines whether a boolean formula in 3CNF form is satisfiable. Such a result would prove that 3SAT $\in \text{P}$ and thus $\text{P} = \text{NP}$. We show Quigley's argument is flawed by providing counterexamples to several lemmas he attempts to use to justify the correctness of his algorithm. We also provide an infinite class of 3CNF formulas that are unsatisfiable but are classified as satisfiable by Quigley's algorithm. In doing so, we prove that Quigley's algorithm fails on certain inputs, and thus his claim that $\text{P} = \text{NP}$ is not established by his paper. |
| title | A Critique of Quigley's "A Polynomial Time Algorithm for 3SAT" |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2510.22985 |