@article{Gordeev_Haeusler_2022, title={Proof Compression and NP Versus PSPACE II: Addendum}, volume={51}, url={https://czasopisma.uni.lodz.pl/bulletin/article/view/8755}, DOI={10.18778/0138-0680.2022.01}, abstractNote={<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>}, number={2}, journal={Bulletin of the Section of Logic}, author={Gordeev, Lew and Haeusler, Edward Hermann}, year={2022}, month={Jan.}, pages={197–205} }