Lew é muito bom. Logo, se tiver engano, é muito sutil. On Mon, Oct 10, 2016 at 4:06 AM, Joao Marcos <botoc...@gmail.com> wrote:
> Mais detalhes em: > > Welcome to NP=PSPACE Area !!! > http://www.tecmf.inf.puc-rio.br/NPPSPACE > > JM > > > ---------- Forwarded message ---------- > > Date: Sat, 8 Oct 2016 10:06:50 -0600 > From: Richard Zach <rz...@ucalgary.ca> > To: <f...@cs.nyu.edu> > > > New on arXiv this week; has anyone read it/formed an opinion? > > https://arxiv.org/abs/1609.09562 > > NP vs PSPACE > Lew Gordeev <https://arxiv.org/find/cs/1/au:+Gordeev_L/0/1/0/all/0/1>, > Edward Hermann Haeusler > <https://arxiv.org/find/cs/1/au:+Haeusler_E/0/1/0/all/0/1> > (Submitted on 30 Sep 2016) > > We present a proof of the conjecture $\mathcal{NP}$ = > $\mathcal{PSPACE}$ by showing that arbitrary tautologies of > Johansson's minimal propositional logic admit "small" polynomial-size > dag-like natural deductions in Prawitz's system for minimal > propositional logic. These "small" deductions arise from standard > "large"\ tree-like inputs by horizontal dag-like compression that is > obtained by merging distinct nodes labeled with identical formulas > occurring in horizontal sections of deductions involved. The > underlying "geometric" idea: if the height, $h\left( \partial \right) > $ , and the total number of distinct formulas, $\phi \left( \partial > \right) $ , of a given tree-like deduction $\partial$ of a minimal > tautology $\rho$ are both polynomial in the length of $\rho$, $\left| > \rho \right|$, then the size of the horizontal dag-like compression is > at most $h\left( \partial \right) \times \phi \left( \partial \right) > $, and hence polynomial in $\left| \rho \right|$. The attached proof > is due to the first author, but it was the second author who proposed > an initial idea to attack a weaker conjecture $\mathcal{NP}= > \mathcal{\mathit{co}NP}$ by reductions in diverse natural deduction > formalisms for propositional logic. That idea included interactive use > of minimal, intuitionistic and classical formalisms, so its practical > implementation was too involved. The attached proof of $ > \mathcal{NP}=\mathcal{PSPACE}$ runs inside the natural deduction > interpretation of Hudelmaier's cutfree sequent calculus for minimal > logic. > > -- > Você está recebendo esta mensagem porque se inscreveu no grupo "LOGICA-L" > dos Grupos do Google. > Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie > um e-mail para logica-l+unsubscr...@dimap.ufrn.br. > Para postar neste grupo, envie um e-mail para logica-l@dimap.ufrn.br. > Visite este grupo em https://groups.google.com/a/ > dimap.ufrn.br/group/logica-l/. > Para ver esta discussão na web, acesse https://groups.google.com/a/ > dimap.ufrn.br/d/msgid/logica-l/CAO6j_LjGy1sfoRZ7tgzZ1Ja97orPipPF79t > o-__vXMQqO%3D%3Dj0A%40mail.gmail.com. > -- fad ahhata alati, awienta Wilushati -- Você está recebendo esta mensagem porque se inscreveu no grupo "LOGICA-L" dos Grupos do Google. Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para logica-l+unsubscr...@dimap.ufrn.br. Para postar neste grupo, envie um e-mail para logica-l@dimap.ufrn.br. Visite este grupo em https://groups.google.com/a/dimap.ufrn.br/group/logica-l/. Para ver esta discussão na web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CA%2BuR7BLwWW8WfeYoRJn0J5A%3DcvnaA26jtmQo_%3DQNMk7dyKXOHA%40mail.gmail.com.
