HackerPapers

arXiv:2201.04118cs.CC

On proof theory in computational complexity: overview

L. Gordeev, E. H. Haeusler

HN submission. Found in a submission link or body. Submitters do not count as commenters in the main ranking; a submission is not an endorsement.

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.

arXiv comments
This is a talk at Logic Colloquium 2021, Poznan, July 2021. arXiv admin note: text overlap with arXiv:2012.04437
Journal reference
DOI
Subjects
cs.CCComputational Complexity

On Hacker News

No comments linking this paper were found in the collected sources. Found in 1 HN submission from Jan 2022 to Jan 2022. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments0 threads

No comments linking this paper were found in the collected sources. Open submission discussions.

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.