HackerPapers

arXiv:1907.03858cs.LO

Proof compression and NP versus PSPACE. Part 2

Lev Gordeev

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

We upgrade [1] to a complete proof of the conjecture NP = PSPACE. [1]: L. Gordeev, E. H. Haeusler, Proof Compression and NP Versus PSPACE, Studia Logica (107) (1): 55-83 (2019)

arXiv comments
12 pages
Journal reference
Bulletin of the Section of Logic (49) (3): 213-230 (2020)
DOI
Subjects
cs.LOLogic in Computer Science

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Jan 2022 to Jan 2022. Found in 1 HN submission from Jul 2019 to Jul 2019. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. On proof theory in computational complexity: overview 1 comment

    • The author claims to have a proof that NP = coNP = PSPACE along the following lines: first they describe their favorite axiomatic logical system, then they claim to have a method to compress quasipolynomial-sized proofs in this system to polynomial-sized proofs. If their claimed…

      ceviView on HNParent context

Submitted to Hacker News

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