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_LjGy1sfoRZ7tgzZ1Ja97orPipPF79to-__vXMQqO%3D%3Dj0A%40mail.gmail.com.
