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.
