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