On proof theory in computational complexity: overview

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.

This is a talk at Logic Colloquium 2021, Poznan, July 2021. arXiv admin note: text overlap with arXiv:2012.04437