Re: [Logica-l] Prova de NP=PSPACE no Bulletin of Section of Logic

[Anderson Beraldo de Araújo]

 compreender a relação entre k-SAT, 2-SAT e
>> HORNSAT porque eles estão na mesma linguagem, os dos últimos são reduções.
>>
>> Abraços,
>>
>> Anderson
>>
>>
>> Em qui., 13 de ago. de 2020 às 11:22, Walter Alexandre Carnielli <
>> walte...@unicamp.br> escreveu:
>>
>>> Colegas:
>>> No intuito de continuar  discussão sobre este importantíssimo
>>> resultado do Lev e do Hermann, só gostaria de notar  que o  argumento
>>> do Anderson apontando  um possível erro esbarra em outras  tentativas
>>> que  também acreditam que  NP = PSPACE .  O artigo (draft) abaixo
>>> define um problema chamado ODDPATH-HORNUNSAT e  mostra que este
>>> problema está em NP e é PSPACE-completo. Como NP ⊆ PSPACE,   e
>>> PSPACE  é fechado por  reduções,  então  NP = PS PACE. O argumento
>>> usa reduções, como é mais usual em questões de complexidade, ao invés
>>> de teoria da prova (ou da demonstração). Não sou capaz de saber se o
>>> argumento é correto, mas  indico  como uma evidência favorável.
>>>
>>> NP versus PSPACE
>>> Frank Vega
>>> https://hal.archives-ouvertes.fr/hal-01196489/file/NP-versus-PSPACE.pdf
>>>
>>> Abraços,
>>> Walter
>>>
>>> Em qui., 13 de ago. de 2020 às 10:17, Anderson Beraldo de Araújo
>>>  escreveu:
>>> >
>>> > Caro Hermann,
>>> >
>>> > Muito obrigado por compartilhar seu trabalho, o qual me parece
>>> interessante.
>>> >
>>> > Ao critério externo, por assim dizer, de prova de igualdade entre
>>> classes de complexidade A e B que o Marcelo mencionou - construir uma
>>> redução apropriada entre problemas completos para as classes A e B (o que
>>> envolve relacionar dois problemas definidos sobre assinaturas distintas) -,
>>> creio ser importante adicionar um critério interno, a saber: construir uma
>>> redução do problema completo estudado em A num problema formulado nos
>>> termos de A (mesma assinatura) mas que seja equivalente a um problema
>>> completo para B. No caso da linguagem da teoria da prova da lógica
>>> intuicionista uma possibilidade para cumprir esse critério interno é
>>> mostrar como o algoritmo de vocês reduz a provabilidade intuicionista
>>> (problema na classe PSPACE) à satisfazibilidade intuicionista (problema na
>>> classe NP). Desse modo, pode-se contornar o problema mencionado por você de
>>> ter que passar pela classe CoNP.
>>> >
>>> > Tendo em vista esse critério interno, que deve ser satisfeito, estimo
>>> que a abordagem de vocês não reduz PSPACE à NP. A razão é a seguinte. A
>>> prova original do Statman de que a provabilidade intuicionista é
>>> PSPACE-completa faz uma redução desse problema formulado em termos do
>>> sistema de dedução natural do Pravitz da lógica minimal intuicionista à
>>> semântica de Kripke da lógica modal S4. Em contrapartida vocês usam em
>>> pontos cruciais a versão do cálculo de sequentes do Huldemaier que não tem
>>> corte. Apesar das pequenas diferenças sintáticas que o sistema do
>>> Huldemaier apresenta, elas expressam saltos de classes de complexidade. No
>>> caso de vocês, esse salto é da classe PSPACE para NP, que é justamente o
>>> que vocês estão tentando provar. Ou seja, sim, parece-me que vocês estão de
>>> fato sugerindo reduções interessantes no tamanho da provabilidade
>>> intuicionista que as colocam na classe NP, mas isso foi possível porque a
>>> própria eliminação do corte embutida no sistema do Huldemaier faz a redução.
>>> >
>>> > Não entrarei em mais detalhes aqui - fico à disposição para
>>> conversarmos em particular. De qualquer forma, para quem desejar dar uma
>>> espiada no assunto, alguns artigos recentes tais como Beckmann & Buss
>>> (2011), Corrected upper bounds for free-cut elimination, que corrige uma
>>> longa sequência de artigos com estimativas erradas dos saltos que mencionei
>>> acima, e Gore & Thomson (2019), A Correct polynomial translation of S4 into
>>> intuitionistic logic, que também corrige uma sequência trabalhos com erros
>>> acerca redutibilidade inicialmente abordada pelo Statman em 1979. Como se
>>> pode ver, existem muitos mal entendidos nessa seara, sendo, portanto, algo
>>> humanamente normal enganar-se. Não estou sugerindo que o trabalho de vocês
>>> está totalmente errado - as reduções em si são interessantes -, mas, até
>>> onde entendo, ele assume um pequenino detalhe que compromete a intenção de
>&g

Re: [Logica-l] Prova de NP=PSPACE no Bulletin of Section of Logic

[Walter Alexandre Carnielli]

no é
>> mostrar como o algoritmo de vocês reduz a provabilidade intuicionista
>> (problema na classe PSPACE) à satisfazibilidade intuicionista (problema na
>> classe NP). Desse modo, pode-se contornar o problema mencionado por você de
>> ter que passar pela classe CoNP.
>> >
>> > Tendo em vista esse critério interno, que deve ser satisfeito, estimo
>> que a abordagem de vocês não reduz PSPACE à NP. A razão é a seguinte. A
>> prova original do Statman de que a provabilidade intuicionista é
>> PSPACE-completa faz uma redução desse problema formulado em termos do
>> sistema de dedução natural do Pravitz da lógica minimal intuicionista à
>> semântica de Kripke da lógica modal S4. Em contrapartida vocês usam em
>> pontos cruciais a versão do cálculo de sequentes do Huldemaier que não tem
>> corte. Apesar das pequenas diferenças sintáticas que o sistema do
>> Huldemaier apresenta, elas expressam saltos de classes de complexidade. No
>> caso de vocês, esse salto é da classe PSPACE para NP, que é justamente o
>> que vocês estão tentando provar. Ou seja, sim, parece-me que vocês estão de
>> fato sugerindo reduções interessantes no tamanho da provabilidade
>> intuicionista que as colocam na classe NP, mas isso foi possível porque a
>> própria eliminação do corte embutida no sistema do Huldemaier faz a redução.
>> >
>> > Não entrarei em mais detalhes aqui - fico à disposição para
>> conversarmos em particular. De qualquer forma, para quem desejar dar uma
>> espiada no assunto, alguns artigos recentes tais como Beckmann & Buss
>> (2011), Corrected upper bounds for free-cut elimination, que corrige uma
>> longa sequência de artigos com estimativas erradas dos saltos que mencionei
>> acima, e Gore & Thomson (2019), A Correct polynomial translation of S4 into
>> intuitionistic logic, que também corrige uma sequência trabalhos com erros
>> acerca redutibilidade inicialmente abordada pelo Statman em 1979. Como se
>> pode ver, existem muitos mal entendidos nessa seara, sendo, portanto, algo
>> humanamente normal enganar-se. Não estou sugerindo que o trabalho de vocês
>> está totalmente errado - as reduções em si são interessantes -, mas, até
>> onde entendo, ele assume um pequenino detalhe que compromete a intenção de
>> reduzir PSPACE à NP. The details matter!
>> >
>> > Abraços,
>> >
>> > Anderson
>> >
>> >
>> > Em qui., 13 de ago. de 2020 às 07:29, Edward Hermann Haeusler <
>> edward.haeus...@gmail.com> escreveu:
>> >>
>> >> Desculpe, respondi só para o Marcelo, mas acho que interessa a quem já
>> me fez essa pergunta também
>> >>
>> >>
>> >> Abracos  e bom dia
>> >>
>> >> Hermann
>> >>
>> >> -- Forwarded message -
>> >> De: Edward Hermann Haeusler 
>> >> Date: qua, 12 de ago de 2020 10:54
>> >> Subject: Re: [Logica-l] Prova de NP=PSPACE no Bulletin of Section of
>> Logic
>> >> To: Marcelo Finger 
>> >>
>> >>
>> >> Obrigado Marcelo,
>> >>
>> >>  De fato passei um tempo tentando explicitar este algoritmo. Como
>> você sabe essas reduções quando compostas passam a ter uma característica
>> combinatória que não é natural, pois o problema intermediário é mediador
>> simplesmente. Como a nossa técnica é proof-theoretical, somos naturalmente
>> obrigados a sair de uma prova, o que faz a redução  ser para CoNP. Neste
>> caso precisariamos chegar em NP. Claro que o nosso resultado garante
>> CoNP=NP, mas não dá para usa-lo. E uma auto-redução polinomial de Taut para
>> Sat não é conhecida.  O que tenho trabalhado mais próximo do mainstream é
>> justamente em certificados polinomiais para grafos não-hamiltonianos. Aí
>> sim, usa-se a redução de Taut para PSPACE via provabilidade intuicionista e
>> junta-se com esse resultado dos certificados polinomiais. Você tem toda a
>> razão, que para convencer o mainstream em CC deve-se ir por esse caminho.
>> Por outro lado, não posso deixar de divulgar algo que tenho certeza que
>> vale, mesmo que o convencimento ainda seja fácil.
>> >>
>> >> Além do mais, o índice de rejeição do resultado é bem alto, coisas
>> como o colapso da hierarquia polinomial e etc.
>> >>
>> >>
>> >> Muito obrigado novamente !!!
>> >>
>> >> Abraços,
>> >>
>> >> Hermann
>> >>
>> >> On Wed, Aug 12, 2020 at 10:35 AM Marcelo Finger 
>> wrote:
>> >>

Re: [Logica-l] Prova de NP=PSPACE no Bulletin of Section of Logic

[Tony Marmo]

Se você verificar, desde a nossa primeira publicação no
>> Studia Logica, isso é feito por um mapeamento das provas em cálculo de
>> sequentes, no fragmento implicacional  do Hudelmaier em Dedução Natural
>> minimal implicacional.
>>
>>O restante do artigo é a descrição do procedimento não-determinístico
>> que extrai uma prova de tamanho polinomial  do dag compactado.  Na versão
>> com certificado, este é uma sequência de alternativas de caminho em uma
>> caminhamento do topo do grafo para a raiz, o certificado escolhe que
>> alternativas formam uma prova válida. Esta parte é que é a novidade em
>> relação ao nosso primeiro
>> artigo publicado no Studia Logica e que tenho trabalhado para fazer de
>> forma determinística sem certificados claro.
>>
>> De importante em relação ao comentário iniciado neste email é que uma
>> reduçao via SAT para minimal implicacional não funciona, pois o
>> procedimento é O(1) para ela. A combinatória de provabilidade em minimal
>> implicacional é bem distinta de SAT clássico ou SAT
>> intuicionista.
>>
>>
>> Abraços
>>
>>
>> Hermann
>>
>> On Thu, Aug 13, 2020 at 10:17 AM Anderson Beraldo de Araújo <
>> andera...@gmail.com> wrote:
>>
>>> Caro Hermann,
>>>
>>> Muito obrigado por compartilhar seu trabalho, o qual me parece
>>> interessante.
>>>
>>> Ao critério externo, por assim dizer, de prova de igualdade entre
>>> classes de complexidade A e B que o Marcelo mencionou - construir uma
>>> redução apropriada entre problemas completos para as classes A e B (o que
>>> envolve relacionar dois problemas definidos sobre assinaturas distintas) -,
>>> creio ser importante adicionar um critério interno, a saber: construir uma
>>> redução do problema completo estudado em A num problema formulado nos
>>> termos de A (mesma assinatura) mas que seja equivalente a um problema
>>> completo para B. No caso da linguagem da teoria da prova da lógica
>>> intuicionista uma possibilidade para cumprir esse critério interno é
>>> mostrar como o algoritmo de vocês reduz a provabilidade intuicionista
>>> (problema na classe PSPACE) à satisfazibilidade intuicionista (problema na
>>> classe NP). Desse modo, pode-se contornar o problema mencionado por você de
>>> ter que passar pela classe CoNP.
>>>
>>> Tendo em vista esse critério interno, que deve ser satisfeito, estimo
>>> que a abordagem de vocês não reduz PSPACE à NP. A razão é a seguinte. A
>>> prova original do Statman de que a provabilidade intuicionista é
>>> PSPACE-completa faz uma redução desse problema formulado em termos do
>>> sistema de dedução natural do Pravitz da lógica minimal intuicionista à
>>> semântica de Kripke da lógica modal S4. Em contrapartida vocês usam em
>>> pontos cruciais a versão do cálculo de sequentes do Huldemaier que não tem
>>> corte. Apesar das pequenas diferenças sintáticas que o sistema do
>>> Huldemaier apresenta, elas expressam saltos de classes de complexidade. No
>>> caso de vocês, esse salto é da classe PSPACE para NP, que é justamente o
>>> que vocês estão tentando provar. Ou seja, sim, parece-me que vocês estão de
>>> fato sugerindo reduções interessantes no tamanho da provabilidade
>>> intuicionista que as colocam na classe NP, mas isso foi possível porque a
>>> própria eliminação do corte embutida no sistema do Huldemaier faz a redução.
>>>
>>> Não entrarei em mais detalhes aqui - fico à disposição para conversarmos
>>> em particular. De qualquer forma, para quem desejar dar uma espiada no
>>> assunto, alguns artigos recentes tais como Beckmann & Buss (2011), 
>>> *Corrected
>>> upper bounds for free-cut elimination*, que corrige uma longa sequência
>>> de artigos com estimativas erradas dos saltos que mencionei acima, e Gore
>>> & Thomson (2019), *A Correct polynomial translation of S4 into
>>> intuitionistic logic*, que também corrige uma sequência trabalhos com
>>> erros acerca redutibilidade inicialmente abordada pelo Statman em 1979.
>>> Como se pode ver, existem muitos mal entendidos nessa seara, sendo,
>>> portanto, algo humanamente normal enganar-se. Não estou sugerindo que o
>>> trabalho de vocês está totalmente errado - as reduções em si são
>>> interessantes -, mas, até onde entendo, ele assume um pequenino detalhe que
>>> compromete a intenção de reduzir PSPACE à NP. The details matter!
>>>
>>> Abraços,
>>>
>>> Anderson
>>>
>>>
>>&

Re: [Logica-l] Prova de NP=PSPACE no Bulletin of Section of Logic

[Anderson Beraldo de Araújo]

ante em relação ao comentário iniciado neste email é que uma
> reduçao via SAT para minimal implicacional não funciona, pois o
> procedimento é O(1) para ela. A combinatória de provabilidade em minimal
> implicacional é bem distinta de SAT clássico ou SAT
> intuicionista.
>
>
> Abraços
>
>
> Hermann
>
> On Thu, Aug 13, 2020 at 10:17 AM Anderson Beraldo de Araújo <
> andera...@gmail.com> wrote:
>
>> Caro Hermann,
>>
>> Muito obrigado por compartilhar seu trabalho, o qual me parece
>> interessante.
>>
>> Ao critério externo, por assim dizer, de prova de igualdade entre classes
>> de complexidade A e B que o Marcelo mencionou - construir uma redução
>> apropriada entre problemas completos para as classes A e B (o que envolve
>> relacionar dois problemas definidos sobre assinaturas distintas) -, creio
>> ser importante adicionar um critério interno, a saber: construir uma
>> redução do problema completo estudado em A num problema formulado nos
>> termos de A (mesma assinatura) mas que seja equivalente a um problema
>> completo para B. No caso da linguagem da teoria da prova da lógica
>> intuicionista uma possibilidade para cumprir esse critério interno é
>> mostrar como o algoritmo de vocês reduz a provabilidade intuicionista
>> (problema na classe PSPACE) à satisfazibilidade intuicionista (problema na
>> classe NP). Desse modo, pode-se contornar o problema mencionado por você de
>> ter que passar pela classe CoNP.
>>
>> Tendo em vista esse critério interno, que deve ser satisfeito, estimo que
>> a abordagem de vocês não reduz PSPACE à NP. A razão é a seguinte. A prova
>> original do Statman de que a provabilidade intuicionista é PSPACE-completa
>> faz uma redução desse problema formulado em termos do sistema de dedução
>> natural do Pravitz da lógica minimal intuicionista à semântica de Kripke da
>> lógica modal S4. Em contrapartida vocês usam em pontos cruciais a versão do
>> cálculo de sequentes do Huldemaier que não tem corte. Apesar das pequenas
>> diferenças sintáticas que o sistema do Huldemaier apresenta, elas expressam
>> saltos de classes de complexidade. No caso de vocês, esse salto é da classe
>> PSPACE para NP, que é justamente o que vocês estão tentando provar. Ou
>> seja, sim, parece-me que vocês estão de fato sugerindo reduções
>> interessantes no tamanho da provabilidade intuicionista que as colocam na
>> classe NP, mas isso foi possível porque a própria eliminação do corte
>> embutida no sistema do Huldemaier faz a redução.
>>
>> Não entrarei em mais detalhes aqui - fico à disposição para conversarmos
>> em particular. De qualquer forma, para quem desejar dar uma espiada no
>> assunto, alguns artigos recentes tais como Beckmann & Buss (2011), *Corrected
>> upper bounds for free-cut elimination*, que corrige uma longa sequência
>> de artigos com estimativas erradas dos saltos que mencionei acima, e Gore
>> & Thomson (2019), *A Correct polynomial translation of S4 into
>> intuitionistic logic*, que também corrige uma sequência trabalhos com
>> erros acerca redutibilidade inicialmente abordada pelo Statman em 1979.
>> Como se pode ver, existem muitos mal entendidos nessa seara, sendo,
>> portanto, algo humanamente normal enganar-se. Não estou sugerindo que o
>> trabalho de vocês está totalmente errado - as reduções em si são
>> interessantes -, mas, até onde entendo, ele assume um pequenino detalhe que
>> compromete a intenção de reduzir PSPACE à NP. The details matter!
>>
>> Abraços,
>>
>> Anderson
>>
>>
>> Em qui., 13 de ago. de 2020 às 07:29, Edward Hermann Haeusler <
>> edward.haeus...@gmail.com> escreveu:
>>
>>> Desculpe, respondi só para o Marcelo, mas acho que interessa a quem já
>>> me fez essa pergunta também
>>>
>>>
>>> Abracos  e bom dia
>>>
>>> Hermann
>>>
>>> -- Forwarded message -
>>> De: Edward Hermann Haeusler 
>>> Date: qua, 12 de ago de 2020 10:54
>>> Subject: Re: [Logica-l] Prova de NP=PSPACE no Bulletin of Section of
>>> Logic
>>> To: Marcelo Finger 
>>>
>>>
>>> Obrigado Marcelo,
>>>
>>>  De fato passei um tempo tentando explicitar este algoritmo. Como
>>> você sabe essas reduções quando compostas passam a ter uma característica
>>> combinatória que não é natural, pois o problema intermediário é mediador
>>> simplesmente. Como a nossa técnica é proof-theoretical, somos naturalmente
>>> obrigados a sair de uma prova, o que faz a redução  ser para CoNP. Neste
&

Re: [Logica-l] Prova de NP=PSPACE no Bulletin of Section of Logic

[Anderson Beraldo de Araújo]

ica de Kripke da lógica modal S4. Em contrapartida vocês usam em
> pontos cruciais a versão do cálculo de sequentes do Huldemaier que não tem
> corte. Apesar das pequenas diferenças sintáticas que o sistema do
> Huldemaier apresenta, elas expressam saltos de classes de complexidade. No
> caso de vocês, esse salto é da classe PSPACE para NP, que é justamente o
> que vocês estão tentando provar. Ou seja, sim, parece-me que vocês estão de
> fato sugerindo reduções interessantes no tamanho da provabilidade
> intuicionista que as colocam na classe NP, mas isso foi possível porque a
> própria eliminação do corte embutida no sistema do Huldemaier faz a redução.
> >
> > Não entrarei em mais detalhes aqui - fico à disposição para conversarmos
> em particular. De qualquer forma, para quem desejar dar uma espiada no
> assunto, alguns artigos recentes tais como Beckmann & Buss (2011),
> Corrected upper bounds for free-cut elimination, que corrige uma longa
> sequência de artigos com estimativas erradas dos saltos que mencionei
> acima, e Gore & Thomson (2019), A Correct polynomial translation of S4 into
> intuitionistic logic, que também corrige uma sequência trabalhos com erros
> acerca redutibilidade inicialmente abordada pelo Statman em 1979. Como se
> pode ver, existem muitos mal entendidos nessa seara, sendo, portanto, algo
> humanamente normal enganar-se. Não estou sugerindo que o trabalho de vocês
> está totalmente errado - as reduções em si são interessantes -, mas, até
> onde entendo, ele assume um pequenino detalhe que compromete a intenção de
> reduzir PSPACE à NP. The details matter!
> >
> > Abraços,
> >
> > Anderson
> >
> >
> > Em qui., 13 de ago. de 2020 às 07:29, Edward Hermann Haeusler <
> edward.haeus...@gmail.com> escreveu:
> >>
> >> Desculpe, respondi só para o Marcelo, mas acho que interessa a quem já
> me fez essa pergunta também
> >>
> >>
> >> Abracos  e bom dia
> >>
> >> Hermann
> >>
> >> -- Forwarded message -
> >> De: Edward Hermann Haeusler 
> >> Date: qua, 12 de ago de 2020 10:54
> >> Subject: Re: [Logica-l] Prova de NP=PSPACE no Bulletin of Section of
> Logic
> >> To: Marcelo Finger 
> >>
> >>
> >> Obrigado Marcelo,
> >>
> >>  De fato passei um tempo tentando explicitar este algoritmo. Como
> você sabe essas reduções quando compostas passam a ter uma característica
> combinatória que não é natural, pois o problema intermediário é mediador
> simplesmente. Como a nossa técnica é proof-theoretical, somos naturalmente
> obrigados a sair de uma prova, o que faz a redução  ser para CoNP. Neste
> caso precisariamos chegar em NP. Claro que o nosso resultado garante
> CoNP=NP, mas não dá para usa-lo. E uma auto-redução polinomial de Taut para
> Sat não é conhecida.  O que tenho trabalhado mais próximo do mainstream é
> justamente em certificados polinomiais para grafos não-hamiltonianos. Aí
> sim, usa-se a redução de Taut para PSPACE via provabilidade intuicionista e
> junta-se com esse resultado dos certificados polinomiais. Você tem toda a
> razão, que para convencer o mainstream em CC deve-se ir por esse caminho.
> Por outro lado, não posso deixar de divulgar algo que tenho certeza que
> vale, mesmo que o convencimento ainda seja fácil.
> >>
> >> Além do mais, o índice de rejeição do resultado é bem alto, coisas como
> o colapso da hierarquia polinomial e etc.
> >>
> >>
> >> Muito obrigado novamente !!!
> >>
> >> Abraços,
> >>
> >> Hermann
> >>
> >> On Wed, Aug 12, 2020 at 10:35 AM Marcelo Finger 
> wrote:
> >>>
> >>>
> >>> Olá Hermann.
> >>>
> >>> Eu admiro sinceramente a sua persistência.
> >>>
> >>> Acho que já mencionei a você que a forma de obter reconhecimento pelo
> seu trabalho é traduzir os resultados de lógicas pouco conhecidas para
> outras fontes que sejam muito mais mainstream.  No caso da conjectura de
> NP=PSPACE, isso se traduz em apresentar um algoritmo que transforma uma
> fórmula satisfatível em QBF em uma fórmula satisfatível na lógica
> proposicional clássica de tamanho apenas polinomialmente maior que a
> fórmula original.  Este resultado é  equivalente a NP=PSPACE, então deve
> ser possível apresentar um tal algoritmo, o que traria aceitação muito mais
> ampla do seu resultado.
> >>>
> >>> []s e continue com o bom trabalho
> >>>
> >>> Marcelo
> >>>
> >>> Em ter., 11 de ago. de 2020 às 12:40, Edward Hermann Haeusler <
> edward.haeus..

Re: [Logica-l] Prova de NP=PSPACE no Bulletin of Section of Logic

[Claus Akira Horodynski Matsushigue]

t;>>
>>>
>>> Abraços
>>>
>>>
>>> Hermann
>>>
>>> On Thu, Aug 13, 2020 at 10:17 AM Anderson Beraldo de Araújo <
>>> andera...@gmail.com> wrote:
>>>
>>>> Caro Hermann,
>>>>
>>>> Muito obrigado por compartilhar seu trabalho, o qual me parece
>>>> interessante.
>>>>
>>>> Ao critério externo, por assim dizer, de prova de igualdade entre
>>>> classes de complexidade A e B que o Marcelo mencionou - construir uma
>>>> redução apropriada entre problemas completos para as classes A e B (o que
>>>> envolve relacionar dois problemas definidos sobre assinaturas distintas) -,
>>>> creio ser importante adicionar um critério interno, a saber: construir uma
>>>> redução do problema completo estudado em A num problema formulado nos
>>>> termos de A (mesma assinatura) mas que seja equivalente a um problema
>>>> completo para B. No caso da linguagem da teoria da prova da lógica
>>>> intuicionista uma possibilidade para cumprir esse critério interno é
>>>> mostrar como o algoritmo de vocês reduz a provabilidade intuicionista
>>>> (problema na classe PSPACE) à satisfazibilidade intuicionista (problema na
>>>> classe NP). Desse modo, pode-se contornar o problema mencionado por você de
>>>> ter que passar pela classe CoNP.
>>>>
>>>> Tendo em vista esse critério interno, que deve ser satisfeito, estimo
>>>> que a abordagem de vocês não reduz PSPACE à NP. A razão é a seguinte. A
>>>> prova original do Statman de que a provabilidade intuicionista é
>>>> PSPACE-completa faz uma redução desse problema formulado em termos do
>>>> sistema de dedução natural do Pravitz da lógica minimal intuicionista à
>>>> semântica de Kripke da lógica modal S4. Em contrapartida vocês usam em
>>>> pontos cruciais a versão do cálculo de sequentes do Huldemaier que não tem
>>>> corte. Apesar das pequenas diferenças sintáticas que o sistema do
>>>> Huldemaier apresenta, elas expressam saltos de classes de complexidade. No
>>>> caso de vocês, esse salto é da classe PSPACE para NP, que é justamente o
>>>> que vocês estão tentando provar. Ou seja, sim, parece-me que vocês estão de
>>>> fato sugerindo reduções interessantes no tamanho da provabilidade
>>>> intuicionista que as colocam na classe NP, mas isso foi possível porque a
>>>> própria eliminação do corte embutida no sistema do Huldemaier faz a 
>>>> redução.
>>>>
>>>> Não entrarei em mais detalhes aqui - fico à disposição para
>>>> conversarmos em particular. De qualquer forma, para quem desejar dar uma
>>>> espiada no assunto, alguns artigos recentes tais como Beckmann & Buss
>>>> (2011), *Corrected upper bounds for free-cut elimination*, que corrige
>>>> uma longa sequência de artigos com estimativas erradas dos saltos que
>>>> mencionei acima, e Gore & Thomson (2019), *A Correct polynomial
>>>> translation of S4 into intuitionistic logic*, que também corrige uma
>>>> sequência trabalhos com erros acerca redutibilidade inicialmente abordada
>>>> pelo Statman em 1979. Como se pode ver, existem muitos mal entendidos nessa
>>>> seara, sendo, portanto, algo humanamente normal enganar-se. Não estou
>>>> sugerindo que o trabalho de vocês está totalmente errado - as reduções em
>>>> si são interessantes -, mas, até onde entendo, ele assume um pequenino
>>>> detalhe que compromete a intenção de reduzir PSPACE à NP. The details
>>>> matter!
>>>>
>>>> Abraços,
>>>>
>>>> Anderson
>>>>
>>>>
>>>> Em qui., 13 de ago. de 2020 às 07:29, Edward Hermann Haeusler <
>>>> edward.haeus...@gmail.com> escreveu:
>>>>
>>>>> Desculpe, respondi só para o Marcelo, mas acho que interessa a quem já
>>>>> me fez essa pergunta também
>>>>>
>>>>>
>>>>> Abracos  e bom dia
>>>>>
>>>>> Hermann
>>>>>
>>>>> -- Forwarded message -
>>>>> De: Edward Hermann Haeusler 
>>>>> Date: qua, 12 de ago de 2020 10:54
>>>>> Subject: Re: [Logica-l] Prova de NP=PSPACE no Bulletin of Section of
>>>>> Logic
>>>>> To: Marcelo Finger 
>>>>>
>>>>>
>>>>> Obrigado Marcelo,
>>>>>
>>>&g

Re: [Logica-l] Prova de NP=PSPACE no Bulletin of Section of Logic

[Edward Hermann Haeusler]

tionistic logic*, que também corrige uma sequência trabalhos com
> erros acerca redutibilidade inicialmente abordada pelo Statman em 1979.
> Como se pode ver, existem muitos mal entendidos nessa seara, sendo,
> portanto, algo humanamente normal enganar-se. Não estou sugerindo que o
> trabalho de vocês está totalmente errado - as reduções em si são
> interessantes -, mas, até onde entendo, ele assume um pequenino detalhe que
> compromete a intenção de reduzir PSPACE à NP. The details matter!
>
> Abraços,
>
> Anderson
>
>
> Em qui., 13 de ago. de 2020 às 07:29, Edward Hermann Haeusler <
> edward.haeus...@gmail.com> escreveu:
>
>> Desculpe, respondi só para o Marcelo, mas acho que interessa a quem já me
>> fez essa pergunta também
>>
>>
>> Abracos  e bom dia
>>
>> Hermann
>>
>> -- Forwarded message -
>> De: Edward Hermann Haeusler 
>> Date: qua, 12 de ago de 2020 10:54
>> Subject: Re: [Logica-l] Prova de NP=PSPACE no Bulletin of Section of Logic
>> To: Marcelo Finger 
>>
>>
>> Obrigado Marcelo,
>>
>>  De fato passei um tempo tentando explicitar este algoritmo. Como
>> você sabe essas reduções quando compostas passam a ter uma característica
>> combinatória que não é natural, pois o problema intermediário é mediador
>> simplesmente. Como a nossa técnica é proof-theoretical, somos naturalmente
>> obrigados a sair de uma prova, o que faz a redução  ser para CoNP. Neste
>> caso precisariamos chegar em NP. Claro que o nosso resultado garante
>> CoNP=NP, mas não dá para usa-lo. E uma auto-redução polinomial de Taut para
>> Sat não é conhecida.  O que tenho trabalhado mais próximo do mainstream é
>> justamente em certificados polinomiais para grafos não-hamiltonianos. Aí
>> sim, usa-se a redução de Taut para PSPACE via provabilidade intuicionista e
>> junta-se com esse resultado dos certificados polinomiais. Você tem toda a
>> razão, que para convencer o mainstream em CC deve-se ir por esse caminho.
>> Por outro lado, não posso deixar de divulgar algo que tenho certeza que
>> vale, mesmo que o convencimento ainda seja fácil.
>>
>> Além do mais, o índice de rejeição do resultado é bem alto, coisas como o
>> colapso da hierarquia polinomial e etc.
>>
>>
>> Muito obrigado novamente !!!
>>
>> Abraços,
>>
>> Hermann
>>
>> On Wed, Aug 12, 2020 at 10:35 AM Marcelo Finger 
>> wrote:
>>
>>>
>>> Olá Hermann.
>>>
>>> Eu admiro sinceramente a sua persistência.
>>>
>>> Acho que já mencionei a você que a forma de obter reconhecimento pelo
>>> seu trabalho é traduzir os resultados de lógicas pouco conhecidas para
>>> outras fontes que sejam muito mais mainstream.  No caso da conjectura de
>>>  NP=PSPACE, isso se traduz em apresentar um algoritmo que transforma uma
>>> fórmula satisfatível em QBF em uma fórmula satisfatível na lógica
>>> proposicional clássica de tamanho apenas polinomialmente maior que a
>>> fórmula original.  Este resultado é  equivalente a NP=PSPACE, então deve
>>> ser possível apresentar um tal algoritmo, o que traria aceitação muito mais
>>> ampla do seu resultado.
>>>
>>> []s e continue com o bom trabalho
>>>
>>> Marcelo
>>>
>>> Em ter., 11 de ago. de 2020 às 12:40, Edward Hermann Haeusler <
>>> edward.haeus...@gmail.com> escreveu:
>>>
>>>>
>>>>  Caros,
>>>>
>>>>  O Bulletin of the section of Logic (Lodz University, Poland)
>>>> publicará em breve a nossa prova, do prof. Lew Gordeev e minha, de que
>>>> NP=PSPACE. O artigo está na seção de EARLY VIEW ainda aguardando a
>>>> publicação em algum volume a partir (exclusive) do atual. O link para
>>>> leitura e críticas é
>>>>
>>>> https://czasopisma.uni.lodz.pl/bulletin/article/view/8169
>>>>
>>>> Temos tb  o DOI:
>>>>
>>>> https://doi.org/10.18778/0138-0680.2020.16
>>>>
>>>>  Agradecemos aos editores do Bulletin pela coragem e
>>>> honestidade de publicar um resultado que pode ter um certo impacto, mesmo
>>>> que, a despeito do nosso esforço, não conseguiu ser exaustivamente avaliado
>>>> pela comunidade acadêmica. Explico, o Bulletin enviou nosso submissão para
>>>> a especialistas (não sei quem são) que após um ano retornaram relatórios de
>>>> avaliação favoráveis, porém relatarem não terem sido capazes de checar
>>>> todas os detalhes e 

Re: [Logica-l] Prova de NP=PSPACE no Bulletin of Section of Logic

[Walter Alexandre Carnielli]

Colegas:
No intuito de continuar  discussão sobre este importantíssimo
resultado do Lev e do Hermann, só gostaria de notar  que o  argumento
do Anderson apontando  um possível erro esbarra em outras  tentativas
que  também acreditam que  NP = PSPACE .  O artigo (draft) abaixo
define um problema chamado ODDPATH-HORNUNSAT e  mostra que este
problema está em NP e é PSPACE-completo. Como NP ⊆ PSPACE,   e
PSPACE  é fechado por  reduções,  então  NP = PS PACE. O argumento
usa reduções, como é mais usual em questões de complexidade, ao invés
de teoria da prova (ou da demonstração). Não sou capaz de saber se o
argumento é correto, mas  indico  como uma evidência favorável.

NP versus PSPACE
Frank Vega
https://hal.archives-ouvertes.fr/hal-01196489/file/NP-versus-PSPACE.pdf

Abraços,
Walter

Em qui., 13 de ago. de 2020 às 10:17, Anderson Beraldo de Araújo
 escreveu:
>
> Caro Hermann,
>
> Muito obrigado por compartilhar seu trabalho, o qual me parece interessante.
>
> Ao critério externo, por assim dizer, de prova de igualdade entre classes de 
> complexidade A e B que o Marcelo mencionou - construir uma redução apropriada 
> entre problemas completos para as classes A e B (o que envolve relacionar 
> dois problemas definidos sobre assinaturas distintas) -, creio ser importante 
> adicionar um critério interno, a saber: construir uma redução do problema 
> completo estudado em A num problema formulado nos termos de A (mesma 
> assinatura) mas que seja equivalente a um problema completo para B. No caso 
> da linguagem da teoria da prova da lógica intuicionista uma possibilidade 
> para cumprir esse critério interno é mostrar como o algoritmo de vocês reduz 
> a provabilidade intuicionista (problema na classe PSPACE) à satisfazibilidade 
> intuicionista (problema na classe NP). Desse modo, pode-se contornar o 
> problema mencionado por você de ter que passar pela classe CoNP.
>
> Tendo em vista esse critério interno, que deve ser satisfeito, estimo que a 
> abordagem de vocês não reduz PSPACE à NP. A razão é a seguinte. A prova 
> original do Statman de que a provabilidade intuicionista é PSPACE-completa 
> faz uma redução desse problema formulado em termos do sistema de dedução 
> natural do Pravitz da lógica minimal intuicionista à semântica de Kripke da 
> lógica modal S4. Em contrapartida vocês usam em pontos cruciais a versão do 
> cálculo de sequentes do Huldemaier que não tem corte. Apesar das pequenas 
> diferenças sintáticas que o sistema do Huldemaier apresenta, elas expressam 
> saltos de classes de complexidade. No caso de vocês, esse salto é da classe 
> PSPACE para NP, que é justamente o que vocês estão tentando provar. Ou seja, 
> sim, parece-me que vocês estão de fato sugerindo reduções interessantes no 
> tamanho da provabilidade intuicionista que as colocam na classe NP, mas isso 
> foi possível porque a própria eliminação do corte embutida no sistema do 
> Huldemaier faz a redução.
>
> Não entrarei em mais detalhes aqui - fico à disposição para conversarmos em 
> particular. De qualquer forma, para quem desejar dar uma espiada no assunto, 
> alguns artigos recentes tais como Beckmann & Buss (2011), Corrected upper 
> bounds for free-cut elimination, que corrige uma longa sequência de artigos 
> com estimativas erradas dos saltos que mencionei acima, e Gore & Thomson 
> (2019), A Correct polynomial translation of S4 into intuitionistic logic, que 
> também corrige uma sequência trabalhos com erros acerca redutibilidade 
> inicialmente abordada pelo Statman em 1979. Como se pode ver, existem muitos 
> mal entendidos nessa seara, sendo, portanto, algo humanamente normal 
> enganar-se. Não estou sugerindo que o trabalho de vocês está totalmente 
> errado - as reduções em si são interessantes -, mas, até onde entendo, ele 
> assume um pequenino detalhe que compromete a intenção de reduzir PSPACE à NP. 
> The details matter!
>
> Abraços,
>
> Anderson
>
>
> Em qui., 13 de ago. de 2020 às 07:29, Edward Hermann Haeusler 
>  escreveu:
>>
>> Desculpe, respondi só para o Marcelo, mas acho que interessa a quem já me 
>> fez essa pergunta também
>>
>>
>> Abracos  e bom dia
>>
>> Hermann
>>
>> -- Forwarded message -
>> De: Edward Hermann Haeusler 
>> Date: qua, 12 de ago de 2020 10:54
>> Subject: Re: [Logica-l] Prova de NP=PSPACE no Bulletin of Section of Logic
>> To: Marcelo Finger 
>>
>>
>> Obrigado Marcelo,
>>
>>  De fato passei um tempo tentando explicitar este algoritmo. Como você 
>> sabe essas reduções quando compostas passam a ter uma característica 
>> combinatória que não é natural, pois o problema intermediário é mediador 
>> simplesmente. Como a nossa técnica é proof-theoretical, 

Re: [Logica-l] Prova de NP=PSPACE no Bulletin of Section of Logic

[Anderson Beraldo de Araújo]

Caro Hermann,

Muito obrigado por compartilhar seu trabalho, o qual me parece interessante.

Ao critério externo, por assim dizer, de prova de igualdade entre classes
de complexidade A e B que o Marcelo mencionou - construir uma redução
apropriada entre problemas completos para as classes A e B (o que envolve
relacionar dois problemas definidos sobre assinaturas distintas) -, creio
ser importante adicionar um critério interno, a saber: construir uma
redução do problema completo estudado em A num problema formulado nos
termos de A (mesma assinatura) mas que seja equivalente a um problema
completo para B. No caso da linguagem da teoria da prova da lógica
intuicionista uma possibilidade para cumprir esse critério interno é
mostrar como o algoritmo de vocês reduz a provabilidade intuicionista
(problema na classe PSPACE) à satisfazibilidade intuicionista (problema na
classe NP). Desse modo, pode-se contornar o problema mencionado por você de
ter que passar pela classe CoNP.

Tendo em vista esse critério interno, que deve ser satisfeito, estimo que a
abordagem de vocês não reduz PSPACE à NP. A razão é a seguinte. A prova
original do Statman de que a provabilidade intuicionista é PSPACE-completa
faz uma redução desse problema formulado em termos do sistema de dedução
natural do Pravitz da lógica minimal intuicionista à semântica de Kripke da
lógica modal S4. Em contrapartida vocês usam em pontos cruciais a versão do
cálculo de sequentes do Huldemaier que não tem corte. Apesar das pequenas
diferenças sintáticas que o sistema do Huldemaier apresenta, elas expressam
saltos de classes de complexidade. No caso de vocês, esse salto é da classe
PSPACE para NP, que é justamente o que vocês estão tentando provar. Ou
seja, sim, parece-me que vocês estão de fato sugerindo reduções
interessantes no tamanho da provabilidade intuicionista que as colocam na
classe NP, mas isso foi possível porque a própria eliminação do corte
embutida no sistema do Huldemaier faz a redução.

Não entrarei em mais detalhes aqui - fico à disposição para conversarmos em
particular. De qualquer forma, para quem desejar dar uma espiada no
assunto, alguns artigos recentes tais como Beckmann & Buss (2011), *Corrected
upper bounds for free-cut elimination*, que corrige uma longa sequência de
artigos com estimativas erradas dos saltos que mencionei acima, e Gore &
Thomson (2019), *A Correct polynomial translation of S4 into intuitionistic
logic*, que também corrige uma sequência trabalhos com erros acerca
redutibilidade inicialmente abordada pelo Statman em 1979. Como se pode
ver, existem muitos mal entendidos nessa seara, sendo, portanto, algo
humanamente normal enganar-se. Não estou sugerindo que o trabalho de vocês
está totalmente errado - as reduções em si são interessantes -, mas, até
onde entendo, ele assume um pequenino detalhe que compromete a intenção de
reduzir PSPACE à NP. The details matter!

Abraços,

Anderson


Em qui., 13 de ago. de 2020 às 07:29, Edward Hermann Haeusler <
edward.haeus...@gmail.com> escreveu:

> Desculpe, respondi só para o Marcelo, mas acho que interessa a quem já me
> fez essa pergunta também
>
>
> Abracos  e bom dia
>
> Hermann
>
> -- Forwarded message -
> De: Edward Hermann Haeusler 
> Date: qua, 12 de ago de 2020 10:54
> Subject: Re: [Logica-l] Prova de NP=PSPACE no Bulletin of Section of Logic
> To: Marcelo Finger 
>
>
> Obrigado Marcelo,
>
>  De fato passei um tempo tentando explicitar este algoritmo. Como você
> sabe essas reduções quando compostas passam a ter uma característica
> combinatória que não é natural, pois o problema intermediário é mediador
> simplesmente. Como a nossa técnica é proof-theoretical, somos naturalmente
> obrigados a sair de uma prova, o que faz a redução  ser para CoNP. Neste
> caso precisariamos chegar em NP. Claro que o nosso resultado garante
> CoNP=NP, mas não dá para usa-lo. E uma auto-redução polinomial de Taut para
> Sat não é conhecida.  O que tenho trabalhado mais próximo do mainstream é
> justamente em certificados polinomiais para grafos não-hamiltonianos. Aí
> sim, usa-se a redução de Taut para PSPACE via provabilidade intuicionista e
> junta-se com esse resultado dos certificados polinomiais. Você tem toda a
> razão, que para convencer o mainstream em CC deve-se ir por esse caminho.
> Por outro lado, não posso deixar de divulgar algo que tenho certeza que
> vale, mesmo que o convencimento ainda seja fácil.
>
> Além do mais, o índice de rejeição do resultado é bem alto, coisas como o
> colapso da hierarquia polinomial e etc.
>
>
> Muito obrigado novamente !!!
>
> Abraços,
>
> Hermann
>
> On Wed, Aug 12, 2020 at 10:35 AM Marcelo Finger 
> wrote:
>
>>
>> Olá Hermann.
>>
>> Eu admiro sinceramente a sua persistência.
>>
>> Acho que já mencionei a você que a forma de obte

Fwd: [Logica-l] Prova de NP=PSPACE no Bulletin of Section of Logic

[Edward Hermann Haeusler]

Desculpe, respondi só para o Marcelo, mas acho que interessa a quem já me
fez essa pergunta também


Abracos  e bom dia

Hermann

-- Forwarded message -
De: Edward Hermann Haeusler 
Date: qua, 12 de ago de 2020 10:54
Subject: Re: [Logica-l] Prova de NP=PSPACE no Bulletin of Section of Logic
To: Marcelo Finger 


Obrigado Marcelo,

 De fato passei um tempo tentando explicitar este algoritmo. Como você
sabe essas reduções quando compostas passam a ter uma característica
combinatória que não é natural, pois o problema intermediário é mediador
simplesmente. Como a nossa técnica é proof-theoretical, somos naturalmente
obrigados a sair de uma prova, o que faz a redução  ser para CoNP. Neste
caso precisariamos chegar em NP. Claro que o nosso resultado garante
CoNP=NP, mas não dá para usa-lo. E uma auto-redução polinomial de Taut para
Sat não é conhecida.  O que tenho trabalhado mais próximo do mainstream é
justamente em certificados polinomiais para grafos não-hamiltonianos. Aí
sim, usa-se a redução de Taut para PSPACE via provabilidade intuicionista e
junta-se com esse resultado dos certificados polinomiais. Você tem toda a
razão, que para convencer o mainstream em CC deve-se ir por esse caminho.
Por outro lado, não posso deixar de divulgar algo que tenho certeza que
vale, mesmo que o convencimento ainda seja fácil.

Além do mais, o índice de rejeição do resultado é bem alto, coisas como o
colapso da hierarquia polinomial e etc.


Muito obrigado novamente !!!

Abraços,

Hermann

On Wed, Aug 12, 2020 at 10:35 AM Marcelo Finger  wrote:

>
> Olá Hermann.
>
> Eu admiro sinceramente a sua persistência.
>
> Acho que já mencionei a você que a forma de obter reconhecimento pelo seu
> trabalho é traduzir os resultados de lógicas pouco conhecidas para outras
> fontes que sejam muito mais mainstream.  No caso da conjectura de
>  NP=PSPACE, isso se traduz em apresentar um algoritmo que transforma uma
> fórmula satisfatível em QBF em uma fórmula satisfatível na lógica
> proposicional clássica de tamanho apenas polinomialmente maior que a
> fórmula original.  Este resultado é  equivalente a NP=PSPACE, então deve
> ser possível apresentar um tal algoritmo, o que traria aceitação muito mais
> ampla do seu resultado.
>
> []s e continue com o bom trabalho
>
> Marcelo
>
> Em ter., 11 de ago. de 2020 às 12:40, Edward Hermann Haeusler <
> edward.haeus...@gmail.com> escreveu:
>
>>
>>  Caros,
>>
>>  O Bulletin of the section of Logic (Lodz University, Poland)
>> publicará em breve a nossa prova, do prof. Lew Gordeev e minha, de que
>> NP=PSPACE. O artigo está na seção de EARLY VIEW ainda aguardando a
>> publicação em algum volume a partir (exclusive) do atual. O link para
>> leitura e críticas é
>>
>> https://czasopisma.uni.lodz.pl/bulletin/article/view/8169
>>
>> Temos tb  o DOI:
>>
>> https://doi.org/10.18778/0138-0680.2020.16
>>
>>  Agradecemos aos editores do Bulletin pela coragem e honestidade
>> de publicar um resultado que pode ter um certo impacto, mesmo que, a
>> despeito do nosso esforço, não conseguiu ser exaustivamente avaliado pela
>> comunidade acadêmica. Explico, o Bulletin enviou nosso submissão para a
>> especialistas (não sei quem são) que após um ano retornaram relatórios de
>> avaliação favoráveis, porém relatarem não terem sido capazes de checar
>> todas os detalhes e que não podem portanto garantir totalmente o resultado.
>> O editor escreveu um remark na primeira página do artigo dizendo que o
>> papel de um periódico científico é também o de divulgar resultados sob
>> estas condições e decidiu pela publicação do artigo. Enfim, o artigo foi
>> avaliado e pede por mais avaliações que serão muito bem vindas
>>
>>Estamos traballhando no sentido de fornecer uma prova mais
>> simples.  Mas aí, já é outra prova.  Esta que está no site do Bulletin não
>> será mais tocada.
>>
>>
>> Abraços,
>>
>> Hermann
>>
>>
>>
>>
>> --
>> Edward Hermann Haeusler
>> Associate Professor
>> Department of Informatics
>> PUC-Rio
>>
>> --
>> 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 ver essa discussão na Web, acesse
>> https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CANzkscGXA%2BOavSp7zewQBzt1VtfOZci2RKDRCKA2AXpekewRpA%40mail.gmail.com
>> <https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CANzkscGXA%2BOavSp7zewQBzt1VtfOZci2RKDRCKA2AXpekewRpA%40mail.gmail.com?utm_medium=email&u

Re: [Logica-l] Prova de NP=PSPACE no Bulletin of Section of Logic

[Valeria de Paiva]

Era exatamente isso que eu queria ter escrito, Mario! Valeu!
abs
Valeria

On Wed, Aug 12, 2020 at 9:41 AM Mario Roberto Folhadela Benevides <
ma...@cos.ufrj.br> wrote:

> Parabéns Hermann!!!
>
> Sua coragem e determinação nos inspiram.
>
> Forte abraço,
>
> Mario
>
> Em qua., 12 de ago. de 2020 às 10:35, Marcelo Finger 
> escreveu:
>
>>
>> Olá Hermann.
>>
>> Eu admiro sinceramente a sua persistência.
>>
>> Acho que já mencionei a você que a forma de obter reconhecimento pelo seu
>> trabalho é traduzir os resultados de lógicas pouco conhecidas para outras
>> fontes que sejam muito mais mainstream.  No caso da conjectura de
>>  NP=PSPACE, isso se traduz em apresentar um algoritmo que transforma uma
>> fórmula satisfatível em QBF em uma fórmula satisfatível na lógica
>> proposicional clássica de tamanho apenas polinomialmente maior que a
>> fórmula original.  Este resultado é  equivalente a NP=PSPACE, então deve
>> ser possível apresentar um tal algoritmo, o que traria aceitação muito mais
>> ampla do seu resultado.
>>
>> []s e continue com o bom trabalho
>>
>> Marcelo
>>
>> Em ter., 11 de ago. de 2020 às 12:40, Edward Hermann Haeusler <
>> edward.haeus...@gmail.com> escreveu:
>>
>>>
>>>  Caros,
>>>
>>>  O Bulletin of the section of Logic (Lodz University, Poland)
>>> publicará em breve a nossa prova, do prof. Lew Gordeev e minha, de que
>>> NP=PSPACE. O artigo está na seção de EARLY VIEW ainda aguardando a
>>> publicação em algum volume a partir (exclusive) do atual. O link para
>>> leitura e críticas é
>>>
>>> https://czasopisma.uni.lodz.pl/bulletin/article/view/8169
>>>
>>> Temos tb  o DOI:
>>>
>>> https://doi.org/10.18778/0138-0680.2020.16
>>>
>>>  Agradecemos aos editores do Bulletin pela coragem e honestidade
>>> de publicar um resultado que pode ter um certo impacto, mesmo que, a
>>> despeito do nosso esforço, não conseguiu ser exaustivamente avaliado pela
>>> comunidade acadêmica. Explico, o Bulletin enviou nosso submissão para a
>>> especialistas (não sei quem são) que após um ano retornaram relatórios de
>>> avaliação favoráveis, porém relatarem não terem sido capazes de checar
>>> todas os detalhes e que não podem portanto garantir totalmente o resultado.
>>> O editor escreveu um remark na primeira página do artigo dizendo que o
>>> papel de um periódico científico é também o de divulgar resultados sob
>>> estas condições e decidiu pela publicação do artigo. Enfim, o artigo foi
>>> avaliado e pede por mais avaliações que serão muito bem vindas
>>>
>>>Estamos traballhando no sentido de fornecer uma prova mais
>>> simples.  Mas aí, já é outra prova.  Esta que está no site do Bulletin não
>>> será mais tocada.
>>>
>>>
>>> Abraços,
>>>
>>> Hermann
>>>
>>>
>>>
>>>
>>> --
>>> Edward Hermann Haeusler
>>> Associate Professor
>>> Department of Informatics
>>> PUC-Rio
>>>
>>> --
>>> 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 ver essa discussão na Web, acesse
>>> https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CANzkscGXA%2BOavSp7zewQBzt1VtfOZci2RKDRCKA2AXpekewRpA%40mail.gmail.com
>>> 
>>> .
>>>
>>
>>
>> --
>>  Marcelo Finger
>>  Departament of Computer Science, IME
>>  University of Sao Paulo
>>  http://www.ime.usp.br/~mfinger
>>  ORCID: https://orcid.org/-0002-1391-1175
>>  ResearcherID: A-4670-2009
>>
>> --
>> 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 ver essa discussão na Web, acesse
>> https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAGG7Aw1xiGU3U%3DoLKKMFKoi07e4iJB93Dx38vFbe5zfrM_upUg%40mail.gmail.com
>> 
>> .
>>
>
>
> --
> Federal University of Rio de Janeiro
> www.cos.ufrj.br/~mario 
>
> --
> 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 ver essa discussão na Web, acesse
> https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAMYO67xvQfDYFw-euT%3D1W%2BXY3BnK90_zuUsxYuu7%3DGO-0aXuCA%40mail.gmail.com
> 
> .
>


-- 
Valeria de Paiva
http://vcvpaiva.github.io/
http:

Re: [Logica-l] Prova de NP=PSPACE no Bulletin of Section of Logic

[Mario Roberto Folhadela Benevides]

Parabéns Hermann!!!

Sua coragem e determinação nos inspiram.

Forte abraço,

Mario

Em qua., 12 de ago. de 2020 às 10:35, Marcelo Finger 
escreveu:

>
> Olá Hermann.
>
> Eu admiro sinceramente a sua persistência.
>
> Acho que já mencionei a você que a forma de obter reconhecimento pelo seu
> trabalho é traduzir os resultados de lógicas pouco conhecidas para outras
> fontes que sejam muito mais mainstream.  No caso da conjectura de
>  NP=PSPACE, isso se traduz em apresentar um algoritmo que transforma uma
> fórmula satisfatível em QBF em uma fórmula satisfatível na lógica
> proposicional clássica de tamanho apenas polinomialmente maior que a
> fórmula original.  Este resultado é  equivalente a NP=PSPACE, então deve
> ser possível apresentar um tal algoritmo, o que traria aceitação muito mais
> ampla do seu resultado.
>
> []s e continue com o bom trabalho
>
> Marcelo
>
> Em ter., 11 de ago. de 2020 às 12:40, Edward Hermann Haeusler <
> edward.haeus...@gmail.com> escreveu:
>
>>
>>  Caros,
>>
>>  O Bulletin of the section of Logic (Lodz University, Poland)
>> publicará em breve a nossa prova, do prof. Lew Gordeev e minha, de que
>> NP=PSPACE. O artigo está na seção de EARLY VIEW ainda aguardando a
>> publicação em algum volume a partir (exclusive) do atual. O link para
>> leitura e críticas é
>>
>> https://czasopisma.uni.lodz.pl/bulletin/article/view/8169
>>
>> Temos tb  o DOI:
>>
>> https://doi.org/10.18778/0138-0680.2020.16
>>
>>  Agradecemos aos editores do Bulletin pela coragem e honestidade
>> de publicar um resultado que pode ter um certo impacto, mesmo que, a
>> despeito do nosso esforço, não conseguiu ser exaustivamente avaliado pela
>> comunidade acadêmica. Explico, o Bulletin enviou nosso submissão para a
>> especialistas (não sei quem são) que após um ano retornaram relatórios de
>> avaliação favoráveis, porém relatarem não terem sido capazes de checar
>> todas os detalhes e que não podem portanto garantir totalmente o resultado.
>> O editor escreveu um remark na primeira página do artigo dizendo que o
>> papel de um periódico científico é também o de divulgar resultados sob
>> estas condições e decidiu pela publicação do artigo. Enfim, o artigo foi
>> avaliado e pede por mais avaliações que serão muito bem vindas
>>
>>Estamos traballhando no sentido de fornecer uma prova mais
>> simples.  Mas aí, já é outra prova.  Esta que está no site do Bulletin não
>> será mais tocada.
>>
>>
>> Abraços,
>>
>> Hermann
>>
>>
>>
>>
>> --
>> Edward Hermann Haeusler
>> Associate Professor
>> Department of Informatics
>> PUC-Rio
>>
>> --
>> 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 ver essa discussão na Web, acesse
>> https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CANzkscGXA%2BOavSp7zewQBzt1VtfOZci2RKDRCKA2AXpekewRpA%40mail.gmail.com
>> 
>> .
>>
>
>
> --
>  Marcelo Finger
>  Departament of Computer Science, IME
>  University of Sao Paulo
>  http://www.ime.usp.br/~mfinger
>  ORCID: https://orcid.org/-0002-1391-1175
>  ResearcherID: A-4670-2009
>
> --
> 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 ver essa discussão na Web, acesse
> https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAGG7Aw1xiGU3U%3DoLKKMFKoi07e4iJB93Dx38vFbe5zfrM_upUg%40mail.gmail.com
> 
> .
>


-- 
Federal University of Rio de Janeiro
www.cos.ufrj.br/~mario 

-- 
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 ver esta discussão na web, acesse 
https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAMYO67xvQfDYFw-euT%3D1W%2BXY3BnK90_zuUsxYuu7%3DGO-0aXuCA%40mail.gmail.com.

Re: [Logica-l] Prova de NP=PSPACE no Bulletin of Section of Logic

[Marcelo Finger]

Olá Hermann.

Eu admiro sinceramente a sua persistência.

Acho que já mencionei a você que a forma de obter reconhecimento pelo seu
trabalho é traduzir os resultados de lógicas pouco conhecidas para outras
fontes que sejam muito mais mainstream.  No caso da conjectura de
 NP=PSPACE, isso se traduz em apresentar um algoritmo que transforma uma
fórmula satisfatível em QBF em uma fórmula satisfatível na lógica
proposicional clássica de tamanho apenas polinomialmente maior que a
fórmula original.  Este resultado é  equivalente a NP=PSPACE, então deve
ser possível apresentar um tal algoritmo, o que traria aceitação muito mais
ampla do seu resultado.

[]s e continue com o bom trabalho

Marcelo

Em ter., 11 de ago. de 2020 às 12:40, Edward Hermann Haeusler <
edward.haeus...@gmail.com> escreveu:

>
>  Caros,
>
>  O Bulletin of the section of Logic (Lodz University, Poland)
> publicará em breve a nossa prova, do prof. Lew Gordeev e minha, de que
> NP=PSPACE. O artigo está na seção de EARLY VIEW ainda aguardando a
> publicação em algum volume a partir (exclusive) do atual. O link para
> leitura e críticas é
>
> https://czasopisma.uni.lodz.pl/bulletin/article/view/8169
>
> Temos tb  o DOI:
>
> https://doi.org/10.18778/0138-0680.2020.16
>
>  Agradecemos aos editores do Bulletin pela coragem e honestidade
> de publicar um resultado que pode ter um certo impacto, mesmo que, a
> despeito do nosso esforço, não conseguiu ser exaustivamente avaliado pela
> comunidade acadêmica. Explico, o Bulletin enviou nosso submissão para a
> especialistas (não sei quem são) que após um ano retornaram relatórios de
> avaliação favoráveis, porém relatarem não terem sido capazes de checar
> todas os detalhes e que não podem portanto garantir totalmente o resultado.
> O editor escreveu um remark na primeira página do artigo dizendo que o
> papel de um periódico científico é também o de divulgar resultados sob
> estas condições e decidiu pela publicação do artigo. Enfim, o artigo foi
> avaliado e pede por mais avaliações que serão muito bem vindas
>
>Estamos traballhando no sentido de fornecer uma prova mais
> simples.  Mas aí, já é outra prova.  Esta que está no site do Bulletin não
> será mais tocada.
>
>
> Abraços,
>
> Hermann
>
>
>
>
> --
> Edward Hermann Haeusler
> Associate Professor
> Department of Informatics
> PUC-Rio
>
> --
> 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 ver essa discussão na Web, acesse
> https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CANzkscGXA%2BOavSp7zewQBzt1VtfOZci2RKDRCKA2AXpekewRpA%40mail.gmail.com
> 
> .
>


-- 
 Marcelo Finger
 Departament of Computer Science, IME
 University of Sao Paulo
 http://www.ime.usp.br/~mfinger
 ORCID: https://orcid.org/-0002-1391-1175
 ResearcherID: A-4670-2009

-- 
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 ver esta discussão na web, acesse 
https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAGG7Aw1xiGU3U%3DoLKKMFKoi07e4iJB93Dx38vFbe5zfrM_upUg%40mail.gmail.com.

Re: [Logica-l] Prova de NP=PSPACE no Bulletin of Section of Logic

[Famadoria]

Boa! Forte abraço!

Sent from my iPhone

> On 11 Aug 2020, at 22:05, Walter Alexandre Carnielli  
> wrote:
> 
> Caro Herrmann.
> 
> parabéns pela perseverança, já  ouvi vc falar  várias  vezes sobre
> isso, e obviamente  não conseguiu passar dos primeiros slides...
> Mas vocês fizeram muito bem em tentar e escolher o Bulletin!
> 
> Uma pergunta: se fossemos buscar um argumento-matemático, em base de
> evidência,  não seria possível pensar em benchmarks,
> que pudessem levar ao convencimento não-matemático sobre o resultado?
> 
> Abraços,
> Walter
> 
> 
>> Em ter., 11 de ago. de 2020 às 18:33, Valeria de Paiva
>>  escreveu:
>> 
>> parabens Hermann por ter conseguido chegar a essa publicacao!
>> abs
>> Valeria
>> 
>>> On Tue, Aug 11, 2020 at 8:40 AM Edward Hermann Haeusler 
>>>  wrote:
>>> 
>>> 
>>> Caros,
>>> 
>>> O Bulletin of the section of Logic (Lodz University, Poland) 
>>> publicará em breve a nossa prova, do prof. Lew Gordeev e minha, de que 
>>> NP=PSPACE. O artigo está na seção de EARLY VIEW ainda aguardando a 
>>> publicação em algum volume a partir (exclusive) do atual. O link para 
>>> leitura e críticas é
>>> 
>>> https://czasopisma.uni.lodz.pl/bulletin/article/view/8169
>>> 
>>> Temos tb  o DOI:
>>> 
>>> https://doi.org/10.18778/0138-0680.2020.16
>>> 
>>> Agradecemos aos editores do Bulletin pela coragem e honestidade de 
>>> publicar um resultado que pode ter um certo impacto, mesmo que, a despeito 
>>> do nosso esforço, não conseguiu ser exaustivamente avaliado pela comunidade 
>>> acadêmica. Explico, o Bulletin enviou nosso submissão para a especialistas 
>>> (não sei quem são) que após um ano retornaram relatórios de avaliação 
>>> favoráveis, porém relatarem não terem sido capazes de checar todas os 
>>> detalhes e que não podem portanto garantir totalmente o resultado. O editor 
>>> escreveu um remark na primeira página do artigo dizendo que o papel de um 
>>> periódico científico é também o de divulgar resultados sob estas condições 
>>> e decidiu pela publicação do artigo. Enfim, o artigo foi avaliado e pede 
>>> por mais avaliações que serão muito bem vindas
>>> 
>>>   Estamos traballhando no sentido de fornecer uma prova mais simples.  
>>> Mas aí, já é outra prova.  Esta que está no site do Bulletin não será mais 
>>> tocada.
>>> 
>>> 
>>> Abraços,
>>> 
>>> Hermann
>>> 
>>> 
>>> 
>>> 
>>> --
>>> Edward Hermann Haeusler
>>> Associate Professor
>>> Department of Informatics
>>> PUC-Rio
>>> 
>>> --
>>> 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 ver essa discussão na Web, acesse 
>>> https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CANzkscGXA%2BOavSp7zewQBzt1VtfOZci2RKDRCKA2AXpekewRpA%40mail.gmail.com.
>> 
>> 
>> 
>> --
>> Valeria de Paiva
>> http://vcvpaiva.github.io/
>> http://www.cs.bham.ac.uk/~vdp/
>> 
>> --
>> 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 ver essa discussão na Web, acesse 
>> https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAESt%3DXub98a7FXFPmN-3HZMZ_ZDxTEh6h3tinzg5nPEOkqwT_A%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 ver esta discussão na web, acesse 
> https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAOrCsLcMEGE7WCt%2B-ZYPGZ0DqGwdAQqMqWTcz-V4ZJ_Xq40_PQ%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 ver esta discussão na web, acesse 
https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/54A5351C-1633-4C1A-96F1-9D27B672C7EA%40gmail.com.

Re: [Logica-l] Prova de NP=PSPACE no Bulletin of Section of Logic

[Walter Alexandre Carnielli]

Caro Herrmann.

 parabéns pela perseverança, já  ouvi vc falar  várias  vezes sobre
isso, e obviamente  não conseguiu passar dos primeiros slides...
Mas vocês fizeram muito bem em tentar e escolher o Bulletin!

Uma pergunta: se fossemos buscar um argumento-matemático, em base de
evidência,  não seria possível pensar em benchmarks,
que pudessem levar ao convencimento não-matemático sobre o resultado?

Abraços,
Walter


Em ter., 11 de ago. de 2020 às 18:33, Valeria de Paiva
 escreveu:
>
> parabens Hermann por ter conseguido chegar a essa publicacao!
> abs
> Valeria
>
> On Tue, Aug 11, 2020 at 8:40 AM Edward Hermann Haeusler 
>  wrote:
>>
>>
>>  Caros,
>>
>>  O Bulletin of the section of Logic (Lodz University, Poland) 
>> publicará em breve a nossa prova, do prof. Lew Gordeev e minha, de que 
>> NP=PSPACE. O artigo está na seção de EARLY VIEW ainda aguardando a 
>> publicação em algum volume a partir (exclusive) do atual. O link para 
>> leitura e críticas é
>>
>> https://czasopisma.uni.lodz.pl/bulletin/article/view/8169
>>
>> Temos tb  o DOI:
>>
>> https://doi.org/10.18778/0138-0680.2020.16
>>
>>  Agradecemos aos editores do Bulletin pela coragem e honestidade de 
>> publicar um resultado que pode ter um certo impacto, mesmo que, a despeito 
>> do nosso esforço, não conseguiu ser exaustivamente avaliado pela comunidade 
>> acadêmica. Explico, o Bulletin enviou nosso submissão para a especialistas 
>> (não sei quem são) que após um ano retornaram relatórios de avaliação 
>> favoráveis, porém relatarem não terem sido capazes de checar todas os 
>> detalhes e que não podem portanto garantir totalmente o resultado. O editor 
>> escreveu um remark na primeira página do artigo dizendo que o papel de um 
>> periódico científico é também o de divulgar resultados sob estas condições e 
>> decidiu pela publicação do artigo. Enfim, o artigo foi avaliado e pede por 
>> mais avaliações que serão muito bem vindas
>>
>>Estamos traballhando no sentido de fornecer uma prova mais simples.  
>> Mas aí, já é outra prova.  Esta que está no site do Bulletin não será mais 
>> tocada.
>>
>>
>> Abraços,
>>
>> Hermann
>>
>>
>>
>>
>> --
>> Edward Hermann Haeusler
>> Associate Professor
>> Department of Informatics
>> PUC-Rio
>>
>> --
>> 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 ver essa discussão na Web, acesse 
>> https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CANzkscGXA%2BOavSp7zewQBzt1VtfOZci2RKDRCKA2AXpekewRpA%40mail.gmail.com.
>
>
>
> --
> Valeria de Paiva
> http://vcvpaiva.github.io/
> http://www.cs.bham.ac.uk/~vdp/
>
> --
> 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 ver essa discussão na Web, acesse 
> https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAESt%3DXub98a7FXFPmN-3HZMZ_ZDxTEh6h3tinzg5nPEOkqwT_A%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 ver esta discussão na web, acesse 
https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAOrCsLcMEGE7WCt%2B-ZYPGZ0DqGwdAQqMqWTcz-V4ZJ_Xq40_PQ%40mail.gmail.com.

Re: [Logica-l] Prova de NP=PSPACE no Bulletin of Section of Logic

[Valeria de Paiva]

parabens Hermann por ter conseguido chegar a essa publicacao!
abs
Valeria

On Tue, Aug 11, 2020 at 8:40 AM Edward Hermann Haeusler <
edward.haeus...@gmail.com> wrote:

>
>  Caros,
>
>  O Bulletin of the section of Logic (Lodz University, Poland)
> publicará em breve a nossa prova, do prof. Lew Gordeev e minha, de que
> NP=PSPACE. O artigo está na seção de EARLY VIEW ainda aguardando a
> publicação em algum volume a partir (exclusive) do atual. O link para
> leitura e críticas é
>
> https://czasopisma.uni.lodz.pl/bulletin/article/view/8169
>
> Temos tb  o DOI:
>
> https://doi.org/10.18778/0138-0680.2020.16
>
>  Agradecemos aos editores do Bulletin pela coragem e honestidade
> de publicar um resultado que pode ter um certo impacto, mesmo que, a
> despeito do nosso esforço, não conseguiu ser exaustivamente avaliado pela
> comunidade acadêmica. Explico, o Bulletin enviou nosso submissão para a
> especialistas (não sei quem são) que após um ano retornaram relatórios de
> avaliação favoráveis, porém relatarem não terem sido capazes de checar
> todas os detalhes e que não podem portanto garantir totalmente o resultado.
> O editor escreveu um remark na primeira página do artigo dizendo que o
> papel de um periódico científico é também o de divulgar resultados sob
> estas condições e decidiu pela publicação do artigo. Enfim, o artigo foi
> avaliado e pede por mais avaliações que serão muito bem vindas
>
>Estamos traballhando no sentido de fornecer uma prova mais
> simples.  Mas aí, já é outra prova.  Esta que está no site do Bulletin não
> será mais tocada.
>
>
> Abraços,
>
> Hermann
>
>
>
>
> --
> Edward Hermann Haeusler
> Associate Professor
> Department of Informatics
> PUC-Rio
>
> --
> 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 ver essa discussão na Web, acesse
> https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CANzkscGXA%2BOavSp7zewQBzt1VtfOZci2RKDRCKA2AXpekewRpA%40mail.gmail.com
> 
> .
>


-- 
Valeria de Paiva
http://vcvpaiva.github.io/
http://www.cs.bham.ac.uk/~vdp/

-- 
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 ver esta discussão na web, acesse 
https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAESt%3DXub98a7FXFPmN-3HZMZ_ZDxTEh6h3tinzg5nPEOkqwT_A%40mail.gmail.com.

[Logica-l] Prova de NP=PSPACE no Bulletin of Section of Logic

[Edward Hermann Haeusler]

 Caros,

 O Bulletin of the section of Logic (Lodz University, Poland)
publicará em breve a nossa prova, do prof. Lew Gordeev e minha, de que
NP=PSPACE. O artigo está na seção de EARLY VIEW ainda aguardando a
publicação em algum volume a partir (exclusive) do atual. O link para
leitura e críticas é

https://czasopisma.uni.lodz.pl/bulletin/article/view/8169

Temos tb  o DOI:

https://doi.org/10.18778/0138-0680.2020.16

 Agradecemos aos editores do Bulletin pela coragem e honestidade de
publicar um resultado que pode ter um certo impacto, mesmo que, a despeito
do nosso esforço, não conseguiu ser exaustivamente avaliado pela comunidade
acadêmica. Explico, o Bulletin enviou nosso submissão para a especialistas
(não sei quem são) que após um ano retornaram relatórios de avaliação
favoráveis, porém relatarem não terem sido capazes de checar todas os
detalhes e que não podem portanto garantir totalmente o resultado. O editor
escreveu um remark na primeira página do artigo dizendo que o papel de um
periódico científico é também o de divulgar resultados sob estas condições
e decidiu pela publicação do artigo. Enfim, o artigo foi avaliado e pede
por mais avaliações que serão muito bem vindas

   Estamos traballhando no sentido de fornecer uma prova mais simples.
Mas aí, já é outra prova.  Esta que está no site do Bulletin não será mais
tocada.


Abraços,

Hermann




-- 
Edward Hermann Haeusler
Associate Professor
Department of Informatics
PUC-Rio

-- 
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 ver esta discussão na web, acesse 
https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CANzkscGXA%2BOavSp7zewQBzt1VtfOZci2RKDRCKA2AXpekewRpA%40mail.gmail.com.