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 <[email protected]>: > You 're welcome, sir! > > Sent from my iPhone > > On 19 Aug 2017, at 09:52, [email protected] wrote: > > Doria: > Obrigado pelo material enviado. > > NC > > Em Sáb 19/08/17 09:50, Famadoria [email protected] escreveu: > > > > Sent from my iPhone > > Begin forwarded message: > > *From:* Joao Marcos <[email protected]> > *Date:* 18 August 2017 04:36:18 GMT-3 > *To:* Lista acadêmica brasileira dos profissionais e estudantes da área > de LOGICA <[email protected]> > *Subject:* *Re: [Logica-l] A Solution of the P versus NP Problem* > *Reply-To:* [email protected] > > 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 > > -- > 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 [email protected]. > Para postar neste grupo, envie um e-mail para [email protected]. > 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 -- 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 [email protected]. Para postar neste grupo, envie um e-mail para [email protected]. 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%2BuR7BJ2pKVO9uwvgTYPw9K0WR4CTS_V6dT76m9w2UCJ%2BopLWQ%40mail.gmail.com.
