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 se
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
___
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
> De qualquer modo, parece que o te
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
___
Logica-l mailing list
Logica-l@dima
Li a coluna do Lipton. O resultado primeiro (se P=NP é verdadeiro então se
prova...) é trivial; vi-o no preprint muito citado e nunca publicado de Shai
ben David e Shai ha Levi.
Mas a hipótese do resultado que Lipton cita, sobre a função de Skolem
associada a P
> Só estranhei um pouco o terceiro:
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
> Nega o primeiro e vc obtem esse.
>
> P≠NP é Pi_2, na formulação usual.
>
>
> 2011/9/19 Rodrigo Freire
>
>> Só estranhei um pouco o terceiro:
>>
>>
>> - Se P ≠ NP é
Nega o primeiro e vc obtem esse.
P≠NP é Pi_2, na formulação usual.
2011/9/19 Rodrigo Freire
> 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
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 compl
