# Search results for: Lew Gordeev

Bulletin of the Section of Logic > 2022 > 51 > 2 > 197-205

Bulletin of the Section of Logic > 2020 > 49 > 3 > 213-230

Electronic Notes in Theoretical Computer Science > 2016 > 323 > C > 181-196

Bulletin of the Section of Logic > 2022 > 51 > 2 > 197-205

In our previous work we proved the conjecture NP = PSPACE by advanced proof theoretic methods that combined Hudelmaier’s cut-free sequent calculus for minimal logic (HSC) with the horizontal compressing in the corresponding minimal Prawitz-style natural deduction (ND). In this Addendum we show how to prove a weaker result NP = coNP without referring to HSC. The underlying idea (due to the second author)...

Bulletin of the Section of Logic > 2020 > 49 > 3 > 213-230

We upgrade [3] to a complete proof of the conjecture NP = PSPACE that is known as one of the fundamental open problems in the mathematical theory of computational complexity; this proof is based on [2]. Since minimal propositional logic is known to be PSPACE complete, while PSPACE to include NP, it suﬃces to show that every valid purely implicational formula ρ has a proof whose weight (= total number...

Electronic Notes in Theoretical Computer Science > 2016 > 323 > C > 181-196

Traditional proof theory of Propositional Logic deals with proofs whose size can be huge. Proof theoretical studies discovered exponential gaps between normal or cut free proofs and their respective non-normal proofs. The use of proof-graphs, instead of trees or lists, for representing proofs is getting popular among proof-theoreticians. Proof-graphs serve as a way to study complexity of propositional...