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.)
2017-08-19 11:30 GMT-03:00 Francisco Antonio Doria <famado...@gmail.com>: > 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 <famado...@gmail.com>: > >> You 're welcome, sir! >> >> Sent from my iPhone >> >> On 19 Aug 2017, at 09:52, ncaco...@terra.com.br wrote: >> >> Doria: >> Obrigado pelo material enviado. >> >> NC >> >> Em Sáb 19/08/17 09:50, Famadoria famado...@gmail.com escreveu: >> >> >> >> Sent from my iPhone >> >> Begin forwarded message: >> >> *From:* Joao Marcos <botoc...@gmail.com> >> *Date:* 18 August 2017 04:36:18 GMT-3 >> *To:* Lista acadêmica brasileira dos profissionais e estudantes da área >> de LOGICA <logica-l@dimap.ufrn.br> >> *Subject:* *Re: [Logica-l] A Solution of the P versus NP Problem* >> *Reply-To:* logica-l@dimap.ufrn.br >> >> On the Edge of Eclipses and P=NP >> https://rjlipton.wordpress.com/2017/08/17/on-the-edge-of-ecl >> ipses-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 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_LgteuUR7%2B%3D8kOqK98Vu0 >> zFmRvYq%2BSvnwjnD7e%2BY4zMPyg%40mail.gmail.com. >> >> > > > -- > fad > > ahhata alati, awienta Wilushati > -- 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%2BuR7BKxOtg59_ZApgv2U%2BEzJ14mEuQOvvmu3RE8B0MJ9%3Dxrbg%40mail.gmail.com.
