O terceiro resultado me foi passado por um grande nome. Gozado, recebo muita msg desse tipo, soube que vc está interessado em assunto tal. Sabia do seguinte?
Deixa eu esclarecer a coisa do Lipton. Se alguma teoria, p.e. ZFC + grandes cardinais seletos, prova P<NP, então P<NP é Pi_1, pois usamos a função de Skolem para por um bound no quantificador existencial, um bound provadamente recursivo. 2011/9/20 Rodrigo Freire <freires...@gmail.com> > De qualquer modo, parece que o terceiro resultado acima implica que P=NP > não é Pi_1. > > > O Lipton coloca como open problem na última linha do artigo dele: "Is P=NP > Pi_1?" > > Por isso estou meio confuso. > > 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
