论文标题
关于计算复杂性的证明理论：概述
On proof theory in computational complexity: overview
论文作者
论文摘要
在[GH1]和[GH2]（另见[GH3]）中，我们提供了平等性NP = Conp = Pspace的完整证明。这些结果是通过新颖的证明理论树到DAG压缩技术可获得的，该技术适合于Prawitz的自然扣除术（ND），用于命题最小逻辑以及相应的Hudelmaier的碎屑序列计算。在本文中，我们提出了证明的概述。
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.
