Li a coluna do Lipton. O resultado primeiro (se P=NP é verdadeiro então se prova...) é trivial; vi-o no preprint muito citado e nunca publicado de Shai ben David e Shai ha Levi.
Mas a hipótese do resultado que Lipton cita, sobre a função de Skolem associada a P<NP, tem o seguinte reforço: A função de Skolem cresce, nos picos, alem de qualquer função recursiva total. Ou seja, cresce como o Busy Beaver. Foi-nos repassadp (argumento de autoridade...) por um dos maiores nomes da lógica. 2011/9/19 Rodrigo Freire <freires...@gmail.com> > Só estranhei um pouco o terceiro: > > > - Se P ≠ NP é independente de ZFC, então é verdadeiro no modelo standard >> para a aritmética (supondo que ZFC o tem). >> > > > Se P = NP for Pi_1 na hierarquia aritmética e P ≠ NP é verdadeiro no modelo > standard, então P ≠ NP é teorema da aritmética pela sigma_1 completude. > Portanto, pelo enunciado acima, P = NP não é Pi_1. Mas eu pensei que isso > era desconhecido: o Lipton afirma que não sabe se isso é o caso aqui: > > http://rjlipton.wordpress.com/2009/05/27/arithmetic-hierarchy-and-pnp/ > > > Não sei se estou perdendo alguma coisa. > > Abraço > Rodrigo > -- 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
