English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

This article shows yet another proof of NP=CoNP$. In a previous article, weproved that NP=PSPACE and from it we can conclude that NP=CoNP immediately. Theformer proof shows how to obtain polynomial and, polynomial in time checkableDag-like proofs for all purely implicational Minimal logic tautologies. Fromthe fact that Minimal implicational logic is PSPACE-complete we get the proofthat NP=PSPACE.  This first proof of NP=CoNP uses Hudelmaier linear upper-bound on the heightof Sequent Calculus minimal implicational logic proofs. In an addendum to theproof of NP=PSPACE, we observe that we do not need to use Hudelmaierupper-bound since any proof of non-hamiltonicity for any graph is linearupper-bounded. By the CoNP-completeness of non-hamiltonicity, we obtain NP=CoNPas a corollary of the first proof. In this article we show the third proof ofCoNP=NP, also providing polynomial size and polynomial verifiable certificatesthat are Dags. They are generated from normal Natural Deduction proofs, linearheight upper-bounded too, by removing redundancy, i.e., repeated parts. Theexistence of repeated parts is a consequence of the redundancy theorem for afamily of super-polynomial proofs in the purely implicational Minimal logic. Itis mandatory to read at least two previous articles to get the details of theproof presented here. The article that proves the redundancy theorem and thearticle that shows how to remove the repeated parts of a normal NaturalDeduction proof to have a polynomial Dag certificate for minimal implicationallogic tautologies.

Yet another argument in favour of NP=CoNP