2024/06/15 by Tianrong Lin, Lin, Tianrong
Computer Science · #03F20 #68Q15 #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2406.10476
openalex publication_date 2024/06/15 · openalex created_date 2024/06/19 · openalex updated_date 2026/07/28
We prove in this paper that there exists a language Ls accepted by some nondeterministic Turing machine that runs within time O(nk) for any positive integer k∈ℕ1 but not accepted by any \rm coNP machines. We further show that Ls is in NP, thereby proving the groundbreaking result that NP≠\rm coNP. The main techniques used in this paper are simulation together with the novel techniques developed in the author's recent work. Our main result has profound implications, such as P\neqNP. Furthermore, if there exists some oracle A such that PA\neNPA=\rm coNPA, we explore the underlying reasons and show that, under this condition and some reasonable assumptions, the set of all \rm coNPA machines is not enumerable. This implies that simulation techniques cannot be applied to the first part of the separation of NPA from \rm coNPA. Finally, a lower bounds result for Frege proof systems is presented (i.e., no Frege proof systems can be polynomially bounded).