Só que o Newton e eu achamos que nem com grandes cardinais. O que pensamos é que a função de Skolem é o passo decisivo. Alguem descobriu, não sei quem, seu crescimento rápido. Isso nos foi comunicado em 94, coisa assim. Levamos uns três anos para descobrir a prova, que exige um truque.
Deixa eu ser mais claro (antes que seu xará brigue comigo de novo...). Define a seguinte funcão: f(n) = 0, se n não codificar uma máquina de Turing polinomial. f(n) = k + 1, onde k é o elemento de Sat que falha pela primeira vez, se a máquina não satisfaz P=NP. f(n) = indefinida, se n satisfaz P=NP. Essa função, talvez parcial, cresce nos picos como o Busy Beaver, ao menos. Mas é obviamente não computável. E aí? Tem versões computáveis, funções tipo Skolem mesmo, para f. 2011/9/20 Rodrigo Freire <freires...@gmail.com> > Agora acho que entendi. O resultado só diz que se P≠NP é independente de > ZFC então P=NP não é Pi_1. > > Sim, se você coneguir uma função de Skolem demonstravelmente recursiva você > reduz para Pi_1. Hipoteses de grandes cardinais podem de fato garantir mais > funções de Skolem. > > 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
