A Solution of the P versus NP Problem

[Márlon Henrique Teixeira]

Recentemente foi publicado um artigo com uma solução para o célebre problema P versus NP. Sei que há pessoas interessadas no assunto aqui, então envio para apreciação e comentários.

https://arxiv.org/pdf/1708.03486.pdf


Att.

Márlon

[Marcelo Finger]

Mais uma tentativa ...

O Scott Aaronson explicou que, no caso deste e de outros problemas
famosos em aberto, a prova deve ser clara e absolutamente convincente.
Além disso, deve responder a critérios básicos do tipo: por que a
prova de N\neq NP não se aplica para 2SAT, como fica o caso de NP =?
coNP, NP =?PSAT, etc.

Eu recebi este artigo hoje mais cedo, mas não tive nem tempo de olhar.

[]s


2017-08-15 11:50 GMT-03:00 Márlon Henrique Teixeira
<marlonhe...@gmail.com>:

> --
> 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+u...@dimap.ufrn.br.
> Para postar nesse grupo, envie um e-mail para logi...@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/4c3c3976-1e37-439d-a8f0-f5745f2c44f2%40dimap.ufrn.br.



--
Marcelo Finger
Departament of Computer Science, IME
University of Sao Paulo
http://www.ime.usp.br/~mfinger

[Joao Marcos]

On Norbert Blum’s claimed proof that P does not equal NP

https://lucatrevisan.wordpress.com/2017/08/15/on-norbert-blums-claimed-proof-that-p-does-not-equal-np/amp/

--

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+unsubscribe@dimap.ufrn.br.

[Joao Marcos]

On the Edge of Eclipses and P=NP
https://rjlipton.wordpress.com/2017/08/17/on-the-edge-of-eclipses-and-pnp/

E para quem quiser uma referência geral para acompanhar as discussões
"em tempo real":
https://cstheory.stackexchange.com/questions/38803/is-norbert-blums-2017-proof-that-p-ne-np-correct


JM

[Francisco Antonio Doria]

Newton e eu temos conversado bastante sobre o paper de Blum. É muito diferente do enfoque usado por nós, e sugerido por Kreisel. Para começar, trabalhamos explicitamente num sistema axiomático (usamos ZFC, em geral). Assim, P≠NP é expresso por uma sentença \Pi_2, que explicitamos. Tal sentença é demonstrável em ZFC se e somente se a função de Skolem associada é provadamente total. 

Aqui começam as complicações. Pois há uma infinidade de possíveis tais funções de Skolem; uma delas, pelo menos, não-computável. E esta função não-computável cresce, nos seus picos, mais que qualquer função recursiva total. E se tal função for total, ZFC não o demonstra (tente fazer uma prova em ZFC da totalidade da função Busy Beaver). 

Ademais, existem muitas questões indecidíveis afetando esses objetos. Uma prova de P<NP (melhor usar < que ≠, quase ilegível) deve mostrar o seguinte: para qualquer sequência infinita de máquinas de Turing poly, sempre haverá uma resposta errada a instância, digamos, de Sat, como input. Ora, podemos gerar algoritmicamente uma tal sequência de máquinas poly P* tal que ``P* é uma sequência de máquinas poly'' seja indecidível. Ou seja, haverá sequências infinitas de máquinas, digamos assim, numa espécie de limbo...

O melhor resultado que obtivemos foi fraco. É um resultado relativo: Se ZFC é sound, então ZFC + ``ZFC é \Sigma_1 sound'' prova que em ZFC não existe demonstração de P<NP. 

2017-08-19 10:09 GMT-03:00 Famadoria <fama...@gmail.com>:

You 're welcome, sir!

Sent from my iPhone

On 19 Aug 2017, at 09:52, ncac...@terra.com.br wrote:

     Doria:
     Obrigado pelo material enviado.

​     NC

Em Sáb 19/08/17 09:50, Famadoria fama...@gmail.com escreveu:

Sent from my iPhone

Begin forwarded message:

--
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+unsubscribe@dimap.ufrn.br.

Para postar neste grupo, envie um e-mail para logi...@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_LgteuUR7%2B%3D8kOqK98Vu0zFmRvYq%2BSvnwjnD7e%2BY4zMPyg%40mail.gmail.com.

--

fad

ahhata alati, awienta Wilushati

[Joao Marcos]

Para uma boa introdução, suave e superficial, ao problema P=?NP e ao
zoológico da complexidade computacional:
https://youtu.be/YX40hbAHx3s


JM

[Francisco Antonio Doria]

Um detalhe: temos um lower bound para algoritmos exponenciais: se a aritmética primitivo recursiva não provar P<NP, então há um algoritmo para tais problemas cujo tempo de operação é pelo menos ~ exp (1/A), A a função de Ackermann. (Já havia comentado isso.)

Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para logica-l+u...@dimap.ufrn.br.

Para postar neste grupo, envie um e-mail para logi...@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_LgteuUR7%2B%3D8kOqK98Vu0zFmRvYq%2BSvnwjnD7e%2BY4zMPyg%40mail.gmail.com.

--

fad

ahhata alati, awienta Wilushati

[Eduardo Ochs]

Alguém podia pôr essas coisas no FAQ da Logica-L

> --
> 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+u...@dimap.ufrn.br.

> Para postar nesse grupo, envie um e-mail para logi...@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%2BuR7BKxOtg59_ZApgv2U%2BEzJ14mEuQOvvmu3RE8B0MJ9%3Dxrbg%40mail.gmail.com.

[Marcelo Finger]

Doria.

V teria algum insight sobre por que existe a transição de fase nos
problemas NP-completos?

Empiricamente, observa-se que ao se gerar aleatoriamente problemas
(por exemplo, SAT), no ponto em que 50% dos problemas são
satisfatíveis e 50%insatisfatíveis, há um pico no tempo médio de se
atingir a decisão. É o ponto de transição de fase. Mas até hoje
ninguém PROVOU que tal fenômeno precisa existir, poderia ser um efeito
apenas da forma como os SAT solvers são implementados hoje em dias. É
um fonômeno robusto: altera-se a implementação e os parêmetros dos
problema, e o fenômeno persiste.

[]s

> --
> 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+u...@dimap.ufrn.br.

> Para postar nesse grupo, envie um e-mail para logi...@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%2BuR7BKxOtg59_ZApgv2U%2BEzJ14mEuQOvvmu3RE8B0MJ9%3Dxrbg%40mail.gmail.com.

[Francisco Antonio Doria]

Oi, Marcelo,

Nunca pensei a respeito; vc teria à mão alguma referência?

O que sei é o seguinte: o problema típico de Sat é resolvido em tempo polinomial pelo algoritmo T das tabelas verdade, isso mesmo. É gozado: alta complexidade de Kolmogorov-Chaitin corresponde a baixa complexidade computacional. São expressões de Sat de baixa complexidade KC as que dão galho e demoram a serem `resolvidas'. Chaitin sabia disso, mas não sei de nenhuma referência.

Num contexto mais amplo, acho que a indecidibilidade que apontei mostra por que esse problema é tão complicado: de repente o sistema axiomático onde estamos não ``vê'' o algoritmo polinomial que faz o milagre de resolver tudo em tempo polinomial... Por isso nos interessou aquele resultado parcial, relativo, que mencionei. A condição que juntamos a ZFC é muito forte: prova inclusive a Consistência (ZFC). E faz desaparecer - se houver - a prova de P<NP em ZFC.

Gdes abcs

>>> envie um e-mail para logica-l+unsubscribe@dimap.ufrn.br.

>>> Para postar neste grupo, envie um e-mail para logi...@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_LgteuUR7%2B%3D8kOqK98Vu0zFmRvYq%2BSvnwjnD7e%2BY4zMPyg%40mail.gmail.com.
>>
>>
>>
>>
>> --
>> fad
>>
>> ahhata alati, awienta Wilushati
>
>
>
>
> --
> 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+unsubscribe@dimap.ufrn.br.

> Para postar nesse grupo, envie um e-mail para logi...@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%2BuR7BKxOtg59_ZApgv2U%2BEzJ14mEuQOvvmu3RE8B0MJ9%3Dxrbg%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+unsubscribe@dimap.ufrn.br.

Para postar neste grupo, envie um e-mail para logi...@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/CABqmzx04-Lwx6f6prmFp8OSPOBGD4yffe3xdY8nh9ASTXs6Q0A%40mail.gmail.com.

[Joao Marcos]

> E para quem quiser uma referência geral para acompanhar as discussões
> "em tempo real":
> https://cstheory.stackexchange.com/questions/38803/is-norbert-blums-2017-proof-that-p-ne-np-correct

A thread parece ter convergido, com o erro sendo localizado no Passo 1
do Teorema 6:
https://cstheory.stackexchange.com/a/38836/16763

Na próxima 3a-feira o próprio Blum se pronunciará a respeito:
https://domino.mpi-inf.mpg.de/internet/events.nsf/3802238747b751e6c12564c10080ba87/c49c4625bee6addfc1258180003ef6a4!OpenDocument

JM