Tava conversando com o Newton sobre isso. Olhei em diagonal o paper. P≠NP tem uma formulação precisa como uma sentença ∏2, ``pra todo x existe y P(x,y),'' P primitivo recursivo. Tais sentenças são demonstráveis numa certa teoria se e somente se provamos que dada função recursiva associada é total, na teoria.
Mas pode ter variantes intuitivas que não ``batem'' com a sentença formal. Tentei ver como ele caracteriza a questão, mas ele remete a livros e artigos aos quais não tenho acesso. Newton, na conversa, disse que pode tb acontecer o que acontece na prova de Wiles para Fermat: a prova não cabe dentro de ZF, ou ZFC, e ninguem sabe se dá para construir uma versão que fique em ZF, ao menos. Outra coisa que vi e não entendi: ele parece que considera instâncias muito complicadas de SAT (existem, claro). Seriam os pontos problemáticos. Ora, tem duas coisas: - Pega uma instância arbitrária de SAT. Então sempre existe um algoritmo polinomial que dá a resposta correta para tal instância. - Suponha uma linguagem (um subconjunto de SAT) onde as tabelas-verdade das instâncias todas têm complexidade máxima de Chaitin (são incompressíveis). Então o algoritmo que calcula tabelas-verdade opera polinomialmente sobre uma tal linguagem. (Tais linguagens, pode-se mostrar, são os casos típicos do problema.) P≠NP não significa a existência de um problema em SAT que seja muito atrapalhado. É, sim, o fato de que, para cada algoritmo polinomial existe uma instância de SAT onde o algoritmo falha. E tem muito galho aí. P.e., posso formular em ZF uma família G de máquinas de Turing que são, todas, polonomiais no modelo standard, mas tais que a sentença ``G é um conjunto de máquinas polinomiais'' seja indecidível em ZF, ou ZFC. Eta bichinho enrolado... De qquer modo, vamos aguardar. 2010/8/9 Adolfo Neto <ado...@utfpr.edu.br> > > 1. P Does Not Equal NP: Understanding Vinay Deolalikar's Proof (matéria > do AOL): http://bit.ly/akN3tT > P != NP (o documento original, em PDF, no site da HP): > http://ow.ly/2n1PT > > ============================================================ > Adolfo Neto > Web: http://www.dainf.ct.utfpr.edu.br/~adolfo > Twitter: http://twitter.com/adolfont > Mestrado em Computação Aplicada: http://www.ppgca.ct.utfpr.edu.br > ============================================================ > > > 2010/8/9 Arthur Buchsbaum <arthurrovabu-log...@yahoo.com.br> > > Caros colegas: >> >> Há uma versão legível de " P ≠ NP", por Vinay Deolalikar, postada no sítio >> Gigapedia, em pdf. >> Não encontrei registro ou ISBN da mesma, tampouco qualquer referência no >> sítio Amazon. >> Dou o liame (ou "link") para quem quiser, ou envio o arquivo como anexo. >> >> a) Arthur Buchsbaum >> >> -----Mensagem original----- >> De: logica-l-boun...@dimap.ufrn.br [mailto:logica-l-boun...@dimap.ufrn.br] >> Em nome de David Deharbe >> Enviada em: segunda-feira, 9 de agosto de 2010 11:46 >> Para: logica-l@dimap.ufrn.br >> Assunto: [Logica-l] P ≠ NP? >> >> (por Vinay Deolalikar) >> >> A quem interessar (e entender!) possa... >> >> http://www.scribd.com/doc/35539144/pnp12pt >> >> Att. >> >> -- David Deharbe >> >> >> _______________________________________________ >> Logica-l mailing list >> Logica-l@dimap.ufrn.br >> http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l >> > > > _______________________________________________ > Logica-l mailing list > Logica-l@dimap.ufrn.br > http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l > > -- fad ahhata alati, awienta Wilushati
_______________________________________________ Logica-l mailing list Logica-l@dimap.ufrn.br http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
