2022•arXiv (Cornell University)Open access
On proof theory in computational complexity: overview
L. Gordeev, Edward Hermann Hæusler
Open full text 0 citations
Abstract
In [GH1] and [GH2] (see also [GH3]) we presented full proof of the equalities NP = coNP = PSPACE. These results have been obtained by the novel proof theoretic tree-to-dag compressing techniques adapted to Prawitz's Natural Deduction (ND) for propositional minimal logic coupled with the corresponding Hudelmaier's cutfree sequent calculus. In this paper we propose an overview of our proofs.
Open-access reader