5 papers
A note on Jerabek's paper "A simplified lower bound for implicational logic"
Lev Gordeev, Edward Hermann Haeusler
In our previous papers we sketched proofs of the equality NP = coNP = PSPACE. These results have been obtained by proof theoretic tree-to-dag compressing techniques adapted to Praw…
Proofs of NP = coNP = PSPACE: Current upgrade
Lev Gordeev, Edward Hermann Haeusler
In this paper we present a more transparent upgrade of our proofs and comment on Jerabek's paper [8].
On P Versus NP
Lev Gordeev
It is shown that graph-theoretic problem CLIQUE can't be solved in polynomial time by any deterministic TM. This upgrades the well-known partial result that claims only monotone un…
Proof compression and NP versus PSPACE. Part 2
Lev Gordeev
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)
Predicative proof theory of PDL and basic applications
Lev Gordeev
Propositional dynamic logic (PDL) is presented in Schütte-style mode as one-sided semiformal tree-like sequent calculus Seq with standard cut rule and the omega-ru…