Bom, aguardo, interessado é claro, os comentários. On Mon, Oct 10, 2016 at 12:49 PM, Marcelo Finger <mfin...@ime.usp.br> wrote:
> Olá. > > O problema é que um resultado tão quente como NP=PSPACE, para ser aceito > pela comunidade hoje em dia, precisa vir com a prova de uma série de > resultados correlatos. > > Em particular, o colapso da hierarquia polinomial deve vir junto com uma > forma de encontrar a equivalência de uma fórmula da lógica booleana > quantificada (QBF), representante de PSPACE, a uma fórmula no fragmento > existencial de QBF, representante de NP, de tamanho apenas polinomialmente > maior, para um polinômio fixo e independente da fórmula e tendo como > parâmetro apenas o tamanho da fórmula. > > E, inclusive, deve ficar claro por que o procedimento não serve para > eliminar a quantificação totalmente, o que faria com que P=PSPACE. > > []s > > Marcelo > > > On 10 October 2016 at 12:18, Francisco Antonio Doria <famado...@gmail.com> > wrote: > >> 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/di >>> map.ufrn.br/group/logica-l/. >>> Para ver esta discussão na web, acesse https://groups.google.com/a/di >>> map.ufrn.br/d/msgid/logica-l/CAO6j_LjGy1sfoRZ7tgzZ1Ja97orPip >>> PF79to-__vXMQqO%3D%3Dj0A%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/di >> map.ufrn.br/group/logica-l/. >> Para ver essa discussão na Web, acesse https://groups.google.com/a/di >> map.ufrn.br/d/msgid/logica-l/CA%2BuR7BLwWW8WfeYoRJn0J5A%3Dc >> vnaA26jtmQo_%3DQNMk7dyKXOHA%40mail.gmail.com >> <https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CA%2BuR7BLwWW8WfeYoRJn0J5A%3DcvnaA26jtmQo_%3DQNMk7dyKXOHA%40mail.gmail.com?utm_medium=email&utm_source=footer> >> . >> > > > > -- > Marcelo Finger > Departament of Computer Science, IME > University of Sao Paulo > http://www.ime.usp.br/~mfinger > > -- > 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/CABqmzx2VjNdLw8TBnoUZjrzZznm4u > etdqmMdeLDB%2BSTKfPQPhA%40mail.gmail.com > <https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CABqmzx2VjNdLw8TBnoUZjrzZznm4uetdqmMdeLDB%2BSTKfPQPhA%40mail.gmail.com?utm_medium=email&utm_source=footer> > . > -- 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%2BuR7BKrCwnJfweJRXRq50Jpzh1kSkxUjrwCvTzrgv6FqqPBVA%40mail.gmail.com.
