Alguém podia pôr essas coisas no FAQ da Logica-L 2017-08-19 17:33 GMT-03:00 Francisco Antonio Doria <[email protected]>: > 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 <[email protected]>: >> >> 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 > > > > > -- > 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 [email protected]. > Para postar nesse grupo, envie um e-mail para [email protected]. > 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.
-- 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/CADs%2B%2B6jLnWG3yRCps2qReXCS1BUy0KjohJ6Xcn6dGnpeBjs1ZQ%40mail.gmail.com.
