Proofs of NP = coNP = PSPACE: Current upgrade

2023/11/28 by Lev Gordeev, Edward Hermann Hæusler, Gordeev, Lev +1
Computer Science · #03 #Advanced Algebra and Logic #Computational Complexity (cs.CC) #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.2311.17939

openalex publication_date 2023/11/28 · openalex created_date 2023/12/02 · openalex updated_date 2026/07/28

Abstract

In this paper we present a more transparent upgrade of our proofs and comment on Jerabek's paper [8].

Related

• Yet another argument in favour of NP=CoNP
• On proof theory in computer science
• On proof theory in computational complexity: overview
• NP vs PSPACE
• DL-PA and DCL-PC: model checking and satisfiability problem are indeed in PSPACE