
Proof compression and NP versus PSPACE: Addendum
We upgrade [1] to a complete proof of the conjecture NP = PSPACE. [1]:...
read it

Proof compression and NP versus PSPACE. Part 2
We upgrade [1] to a complete proof of the conjecture NP = PSPACE. [1]:...
read it

On proof theory in computer science
The subject logic in computer science should entail proof theoretic appl...
read it

Yet another argument in favour of NP=CoNP
This article shows yet another proof of NP=CoNP. In a previous article, ...
read it

Going from the huge to the small: Efficient succinct representation of proofs in Minimal implicational logic
A previous article shows that any linear height bounded normal proof of ...
read it

Stoquastic PCP vs. Randomness
The derandomization of MA, the probabilistic version of NP, is a long st...
read it

Subatomic systems need not be subatomic
Subatomic systems were recently introduced to identify the structural pr...
read it
Proof Compression and NP Versus PSPACE II: Addendum
In [3] we proved the conjecture NP = PSPACE by advanced proof theoretic methods that combined Hudelmaier's cutfree sequent calculus for minimal logic (HSC) [5] with the horizontal compressing in the corresponding minimal Prawitzstyle natural deduction (ND) [6]. 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) is to omit full minimal logic and compress only " normal treelike ND refutations of the existence of Hamiltonian cycles in given nonHamiltonian graphs, since the Hamiltonian graph problem in NPcomplete. Thus, loosely speaking, the proof of NP = coNP can be obtained by HSCelimination from our proof of NP = PSPACE [3]. [3] L. Gordeev, E. H. Haeusler, Proof Compression and NP Versus PSPACE II, Bulletin of the Section of Logic (49) (3): 213230 (2020) http://dx.doi.org/10.18788/01380680.2020.16 [1907.03858] [5] J. Hudelmaier, An O (n log n)space decision procedure for intuitionistic propositional logic, J. Logic Computat. (3): 113 (1993) [6] D. Prawitz, Natural deduction: a prooftheoretical study. Almqvist Wiksell, 1965
READ FULL TEXT
Comments
There are no comments yet.