TY - JOUR
AU - Gordeev, Lew
AU - Haeusler, Edward Hermann
PY - 2022/01/07
Y2 - 2022/12/06
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 -