A Critique of Lin's "On $\text{NP}$ versus $\text{coNP}$ and Frege Systems"
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912367235825664 |
|---|---|
| author | DeJesse, Nicholas Lyudovyk, Spencer Pai, Dhruv Reidy, Michael |
| author_facet | DeJesse, Nicholas Lyudovyk, Spencer Pai, Dhruv Reidy, Michael |
| contents | In this paper, we examine Lin's "On NP versus coNP and Frege Systems" [Lin25]. Lin claims to prove that $\text{NP} \neq \text{coNP}$ by constructing a language $L_d$ such that $L_d \in \text{NP}$ but $L_d \notin \text{coNP}$. We present a flaw in Lin's construction of $D$ (a nondeterministic Turing machine that supposedly recognizes $L_d$ in polynomial time). We also provide a proof that $L_d \not\in \text{NP}$. In doing so, we demonstrate that Lin's claim that $\text{NP} \neq \text{coNP}$ is not established by his paper. In addition, we note that a number of further results that Lin claims are not validly established by his paper. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_05658 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Critique of Lin's "On $\text{NP}$ versus $\text{coNP}$ and Frege Systems" DeJesse, Nicholas Lyudovyk, Spencer Pai, Dhruv Reidy, Michael Computational Complexity In this paper, we examine Lin's "On NP versus coNP and Frege Systems" [Lin25]. Lin claims to prove that $\text{NP} \neq \text{coNP}$ by constructing a language $L_d$ such that $L_d \in \text{NP}$ but $L_d \notin \text{coNP}$. We present a flaw in Lin's construction of $D$ (a nondeterministic Turing machine that supposedly recognizes $L_d$ in polynomial time). We also provide a proof that $L_d \not\in \text{NP}$. In doing so, we demonstrate that Lin's claim that $\text{NP} \neq \text{coNP}$ is not established by his paper. In addition, we note that a number of further results that Lin claims are not validly established by his paper. |
| title | A Critique of Lin's "On $\text{NP}$ versus $\text{coNP}$ and Frege Systems" |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2505.05658 |