2025/05/08 by DeJesse, Nicholas, Lyudovyk, Spencer, Pai, Dhruv +1
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2505.05658
In this paper, we examine Lin's "On NP versus coNP and Frege Systems" [Lin25]. Lin claims to prove that NP ≠ coNP by constructing a language Ld such that Ld ∈ NP but Ld ∉ coNP. We present a flaw in Lin's construction of D (a nondeterministic Turing machine that supposedly recognizes Ld in polynomial time). We also provide a proof that Ld \not∈ NP. In doing so, we demonstrate that Lin's claim that NP ≠ 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.