No primeiro, reduzimos P=NP de Sigma_2 para Pi_1, e tiramos a conclusão via um lema de Kreisel.
2011/9/20 Francisco Antonio Doria <famado...@gmail.com> > Nega o primeiro e vc obtem esse. > > P≠NP é Pi_2, na formulação usual. > > > 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 > > -- 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
