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á na classe NP. Para isso, precisamos mostrar que, quando o elemento dado possui a propriedade, existe um passo não determinístico (um chute) que gera uma _estrutura auxiliar_ e com essa estrutura auxiliar e o elemento dado, podemos verificar e um número polinomial de passos que o elemento possui a propriedade. Por exemplo, se o elemento é uma fórmula na lógica proposicional clássica, a propriedade é ser satisfazível, então a estrutura auxiliar é uma valoração das variáveis atốmicas, com a qual mostramos em tempo linear no número de átomos da fórmula que esta é satisfazível. Há uma fundamental assimetria aqui, pois no caso de a fórmula ser insatisfazível não precisamos mostrar nada. b) Que ele é NP-difícil. Para isso, basta reduzir polinomialmente a decisão de UM problema NP-completo na decisão dada. Aqui a gente precisa apresentar UMA redução, e ganha "de grátis" a existência de reduções para todos os outros problemas NP-completos. Na realidade, não é "de grátis", mas pela transitividade de reduções polinomiais, que também é polinomial. Cook demonstrou que fórmulas da LPC simulam qqer problema de decisão em máquinas de turing não-determinística de tempo polinomial, de forma que dado um problema em uma máquina de Turing MT em NP, computa-se uma fórmula A tal que a MT pára com resposta SIM sse a fórmula A é SAT. Ou seja, todo problema em NP se reduz a SAT. []s -- 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/CABqmzx3U-TUoaE014DJ6RAm4KLBk%2BGUcyWF9g2SN3OV%3Dy1kZFQ%40mail.gmail.com.
