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 _______________________________________________ Logica-l mailing list Logica-l@dimap.ufrn.br http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
