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.oliveira@student.u
ni-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/di
> map.ufrn.br/group/logica-l/.
> Para ver esta discussão na web, acesse https://groups.google.com/a/di
> map.ufrn.br/d/msgid/logica-l/87a864gfn1.fsf%40camelot.oliveira.
>
--
fad
ahhata alati, awienta Wilushati
--
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/CA%2BuR7BKLad8ocCVePEPWNHd8aNAYX%3DHG0FOY50F%3DtEu-6G7Zjg%40mail.gmail.com.
