Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

Proof Compression and NP Versus PSPACE II

Lew GordeevEdward Hermann Haeusler — 2020

Bulletin of the Section of Logic

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 suffices to show that every valid purely implicational formula ρ has a proof whose weight (= total number of symbols) and time complexity of the provability involved are both polynomial in the weight of...

Page 1

Download Results (CSV)