Prezado Samuel,
Você teria que procurar um enunciado que não seja absoluto para o universo
construtível L. De fato, temos o seguinte resultado, já aludido em uma das
respostas nesse link que você enviou:
- Se S é um enunciado absoluto para L em ZF, e S é demonstrável em ZFC,
então S é demonstráve
Um dos exemplos: um real do qual não podemos calcular um só dígito.
Sent from my iPhone
> On 23 May 2017, at 09:58, Marcelo Finger wrote:
>
> Oi Samuel.
>
>> A princípio eu disse pra ele, há alguns meses, que os argumentos em
>> Computação devem ser
>> todos construtivos, assim não faria sen
Oi Samuel.
> A princípio eu disse pra ele, há alguns meses, que os argumentos em
> Computação devem ser
> todos construtivos, assim não faria sentido aplicar o Axioma da Escolha em
> Computação.
Não concordo. Se v consegue apresentar uma propriedade desconhecida
de um problema interessante, po
Oi Hermógenes.
> Como poderíamos mostrar que um problema é NP-completo sem exibir uma
> redução?
Para mostrar que um problema de DECISÂO é NP-completo (a classe NP só
é definida para problemas que decidem se um elemento possui uma dada
propriedade), precisamos mostrar duas coisas:
a) Que ele est
Há uns vinte anos soube que Solovay discutiu várias versões do número Omega
de Chaitin, com propriedades estranhíssimas. Discuti a coisa com o Newton e
saímos à cata de outros exemplos agualmente peculiares. Newton sugeriu uma
versão do Omega cuja construção invocava explicitamente o Axioma da
Esco
Marcelo Finger escreveu:
> 2017-05-22 22:00 GMT-03:00 Famadoria :
>> Tem casos em que a gente pode provar que há um algoritmo sem exibi-lo.
>
> Certamente. Basta mostrar que um problema é NP-completo que segue que
> há uma redução polinomial para qualquer outro problema NP-completo.
> Encontrar
