OI Eduardo. Pelo contrário, tem várias pessoas tentando entender. O que eu vi por enquanto é a estratégia da prova. Eles estão criando um meio de compactar provas na lógica minimal (que é PSPACE-completo) para provas de tamanho sempre polinomial. Assim sendo, o passo (não-determinístico) inicial da prova poderia ser chutar uma prova de tamanho polinomial, que é verificada tb em tempo polinomial. Logo a compactação faz PSPACE colapsar para NP.
Só não entendi ainda como funciona essa compactação ... Marcelo On 11 October 2016 at 12:12, Eduardo Ochs <eduardoo...@gmail.com> wrote: > Vou contar pro Hermann que ninguém aqui quer ler o paper dele > > On Tue, Oct 11, 2016 at 12:09 PM, Francisco Antonio Doria > <famado...@gmail.com> wrote: > > Gostaria de poder contribuir, mas desconheço as técnicas usadas. > > > > On Tue, Oct 11, 2016 at 10:24 AM, Joao Marcos <botoc...@gmail.com> > wrote: > >> > >> Bem, certamente os nossos colegas estão precisando menos da nossa > >> *confiança* na correção do resultado e mais da *leitura competente* do > >> material que produziram... > >> > >> A propósito, Hermann pediu para avisar que a página > >> http://www.tecmf.inf.puc-rio.br/NPPSPACE > >> foi atualizada com material explicativo, e para dizer que "há alguns > >> problemas de formatação (código tex misturado com wiki), mas é > >> perfeitamente inteligível". > >> > >> 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_LgdR%2BQkG_6EXQQXdmj0rttxforXPH_u6Hzfs%3DGCj46mVw%40mail.gmail.com > . > > > > > > > > > > -- > > fad > > > > ahhata alati, awienta Wilushati > > > > -- > > Você recebeu essa mensagem porque está inscrito 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 nesse grupo, envie um e-mail para logica-l@dimap.ufrn.br. > > Acesse esse grupo em > > https://groups.google.com/a/dimap.ufrn.br/group/logica-l/. > > Para ver essa discussão na Web, acesse > > https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CA% > 2BuR7BL0z1UpyGcRNXOD8mknR%3DO9xhPx%3Dy5HeiZLyiOA_4ffxg%40mail.gmail.com. > > -- > 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/CADs%2B%2B6hSF9nqaNHJ%2Bha4Mw_rvpQ%3DB- > AqRUH7iyCkh9Bdsk8E2A%40mail.gmail.com. > -- Marcelo Finger Departament of Computer Science, IME University of Sao Paulo http://www.ime.usp.br/~mfinger -- 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/CABqmzx3bpPk2kwkjru--MRQknVLtxQ2mHcRnKJHuyM%3DQdtCruQ%40mail.gmail.com.
