TY - JOUR AU - Gordeev, Lew AU - Haeusler, Edward Hermann PY - 2022/01/07 Y2 - 2024/03/28 TI - Proof Compression and NP Versus PSPACE II: Addendum JF - Bulletin of the Section of Logic JA - B Sect Log VL - 51 IS - 2 SE - Research Article DO - 10.18778/0138-0680.2022.01 UR - https://czasopisma.uni.lodz.pl/bulletin/article/view/8755 SP - 197-205 AB - <p>In our previous work we proved the conjecture <strong>NP = PSPACE</strong> by advanced proof theoretic methods that combined Hudelmaier’s cut-free sequent calculus for minimal logic (HSC) with the horizontal compressing in the corresponding minimal Prawitz-style natural deduction (ND). In this Addendum we show how to prove a weaker result <strong>NP = coNP</strong> without referring to HSC. The underlying idea (due to the second author) is to omit full minimal logic and compress only “naive” normal tree-like ND refutations of the existence of Hamiltonian cycles in given non-Hamiltonian graphs, since the Hamiltonian graph problem in NPcomplete. Thus, loosely speaking, the proof of<strong> NP = coNP</strong> can be obtained by HSC-elimination from our proof of <strong>NP = PSPACE</strong>.</p> ER -