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, pouco importa se a prova é construtiva ou
não. Na hora de buscar um algoritmo (construtivo) é bom saber que a
propriedade que se quer demonstrar é verdadeira.
Tem muita prova importante de complexidade de problemas em que os
algoritmos são totalmente não-determinísticos, e a geração de um
algoritmo não trivial (ou seja, que não gera-e-testa todos os casos)
involve a exploração de OUTRAS propriedades. Mesmo assim, a prova
original é considerada totalmente válida.
Eu mesmo me deparei com um caso assim recentemente. Havia uma prova
de que um problema de decisão envolvendo Quantificadores de Contagem
era NP-completo, mas o algoritmo que o Ian Pratt-Hartman apresentou
era totalmente não-determinístico, e eu usei uma modificação do
algoritmo branch-and-bound de programação linear inteira para gerar um
algoritmo determinístico.
[]s
2017-05-23 9:42 GMT-03:00 Francisco Antonio Doria <famado...@gmail.com>:
> 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 Escolha.
> Isto foi publicado pela gente nalgum canto, não lembro exato onde.
>
> 2017-05-23 5:07 GMT-03:00 Hermógenes Oliveira
> <hermogenes.olive...@student.uni-tuebingen.de>:
>>
>> Marcelo Finger <mfin...@ime.usp.br> escreveu:
>>
>> > 2017-05-22 22:00 GMT-03:00 Famadoria <famado...@gmail.com>:
>> >> 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 estas reduções são outros 500.
>>
>> Olá, Marcelo.
>>
>> Esta é uma pergunta sincera (não retórica):
>>
>> Como poderíamos mostrar que um problema é NP-completo sem exibir uma
>> redução? Pergunto isso apenas porque todas as demonstrações desse tipo
>> que eu conheço exibem a redução. Você poderia citar algum contraexemplo
>> (referência bibliográfica)?
>>
>> Quando penso a respeito, tenho dificuldade de vislumbrar como uma
>> demonstração dessas funcionaria. Para demonstrar que um problema é
>> NP-completo, além de demonstrar que o problema pertence à classe NP,
>> seria necessário demonstrar que o problema é NP-Hard ("NP-difícil" ?).
>> Até onde consigo ver, a única forma de fazer isso seria mostrar uma
>> redução polinomial do problema a outro problema comprovadamente
>> NP-completo ou relacionar diretamente o espaço das soluções do problema
>> com o modelo de computação subjacente (normalmente, máquinas de Turing)
>> como fez Cook com o SAT no artigo de 71. Existiria uma outra maneira?
>> O que significaria, neste contexto, demonstratar que existe uma redução
>> (construção, algorítimo) polinomial do problema sem exibir tal redução
>> (construção, algorítimo)? Se você conhece algum exemplo, eu estaria
>> muito interessado.
>>
>> Consigo ver que, para resultados negativos, não seria necessário exibir
>> um algorítimo, pois poderíamos supor que há uma redução e extrair daí
>> uma contradição, mas esse tipo de raciocínio é construtivamente aceito.
>>
>> Obviamente, se o problema é indecidível, ter uma redução (por exemplo,
>> para o problema da parada) não significa ter um algorítimo *para
>> solucionar do problema*. Mas, para o caso de problemas NP-completos,
>> não consigo ver como seria possível demonstrar NP-completude sem
>> fornecer as reduções e obter daí um algorítimo, possivelmente com ajuda
>> de resultados e reduções já conhecidas.
>>
>> --
>> Hermógenes Oliveira
>>
>> --
>> Você está recebendo esta mensagem porque se inscreveu no grupo "LOGICA-L"
>> dos Grupos do Google.
>> Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie
>> um e-mail para logica-l+unsubscr...@dimap.ufrn.br.
>> Para postar neste grupo, envie um e-mail para logica-l@dimap.ufrn.br.
>> Visite este grupo em
>> https://groups.google.com/a/dimap.ufrn.br/group/logica-l/.
>> Para ver esta discussão na web, acesse
>> https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/87a864gfn1.fsf%40camelot.oliveira.
>
>
>
>
> --
> fad
>
> ahhata alati, awienta Wilushati
>
> --
> Você recebeu essa mensagem porque está inscrito no grupo "LOGICA-L" dos
> Grupos do Google.
> Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie
> um e-mail para logica-l+unsubscr...@dimap.ufrn.br.
> Para postar nesse grupo, envie um e-mail para logica-l@dimap.ufrn.br.
> Acesse esse grupo em
> https://groups.google.com/a/dimap.ufrn.br/group/logica-l/.
> Para ver essa discussão na Web, acesse
> https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CA%2BuR7BKLad8ocCVePEPWNHd8aNAYX%3DHG0FOY50F%3DtEu-6G7Zjg%40mail.gmail.com.
--
Marcelo Finger
Departament of Computer Science, IME
University of Sao Paulo
http://www.ime.usp.br/~mfinger
--
Você está recebendo esta mensagem porque se inscreveu no grupo "LOGICA-L" dos
Grupos do Google.
Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um
e-mail para logica-l+unsubscr...@dimap.ufrn.br.
Para postar neste grupo, envie um e-mail para logica-l@dimap.ufrn.br.
Visite este grupo em https://groups.google.com/a/dimap.ufrn.br/group/logica-l/.
Para ver esta discussão na web, acesse
https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CABqmzx3KW_fPkKr2LOpcZnN%2BfZbCrf52WfWkRZPTOb4WQnanRw%40mail.gmail.com.
