Por que é importante provar que um problema é NP-completo?

Respostas:

26

Ali, boa pergunta.

Suponha que você queira mostrar que algum problema P é computacionalmente difícil. Agora, você pode conjeturar que P é difícil apenas com base no fato de que ainda não temos algoritmos eficientes. Mas essa é uma evidência bastante frágil, não? Pode ser que tenhamos perdido uma boa maneira de olhar para P, o que tornaria muito fácil sua solução. Portanto, para conjeturar que P é difícil, gostaríamos de acumular mais evidências. As reduções fornecem uma ferramenta para fazer exatamente isso! Se pudermos reduzir algum outro problema natural Q a P, mostramos que P é pelo menos tão difícil quanto Q. Mas Q pode ser um problema de alguma área completamente diferente da matemática, e as pessoas podem ter lutado por décadas para resolver Q também . Assim, podemos ver nossa falha em encontrar um algoritmo eficiente para Q ser evidência de que P é difícil. Se tivermos muitos desses Q '

É exatamente isso que a teoria da completude NP fornece. Se você provar que seu problema está completo como NP, vinculou sua dureza à dureza de centenas de outros problemas, cada um com interesse significativo para várias comunidades. Assim, moralmente falando, você pode ter certeza de que seu problema é realmente difícil.

arnab
fonte
Portanto, o objetivo inicial é encontrar um algoritmo eficiente para P, mas como isso parece inatingível, assume-se que P é computacionalmente difícil e, em seguida, suas respostas explicam o resto?
Ali
Queremos mostrar que nosso problema P é computacionalmente difícil, mas não queremos assumir que P é difícil provar que P é difícil :) Em vez disso, se você provar que P é NP-completo (ou mesmo NP-difícil, mas vamos ignorar a distinção aqui), você mostrou que se qualquer um dentre centenas de problemas já bem examinados for difícil, P também será difícil. Isso ocorre porque, se houvesse um algoritmo eficiente para P, também haveria algoritmos eficientes para cada uma das centenas de problemas.
arnab
4
@ Ali: eu sugiro fortemente que você olhe para um livro introdutório da teoria da complexidade. Este site não é realmente um fórum para essas perguntas, mas mais para perguntas em nível de pesquisa.
arnab
5
@ Ali: eu definitivamente recomendo que você leia Garey e Johnson . O famoso desenho animado do livro é imperdível!
Tsuyoshi Ito
9

Provando um problema O NP-Complete é um sucesso de pesquisa, pois libera você de procurar uma solução eficiente e exata para o problema geral que você está estudando. Isso prova que seu problema é membro de uma classe de problemas tão difícil que ninguém foi capaz de encontrar um algoritmo eficiente e exato para nenhum dos problemas, e essa solução para qualquer um desses problemas implicaria uma solução para todos os problemas. problemas

Geralmente é um trampolim, porque seu problema ainda está lá - você simplesmente precisa relaxar suas necessidades. Geralmente, as pessoas tentam descobrir como relaxar um ou mais dos itens "eficiente", "exato" ou "geral". Ineficiente e exato e geral é a tentativa de encontrar constantes cada vez melhores no expoente para esses algoritmos. Eficiente e inexato e geral é o estudo de algoritmos de aproximação. Eficiente e exato, mas não geral é o estudo da rastreabilidade de parâmetros fixos e a busca por subclasses de entrada para as quais algoritmos eficientes podem ser encontrados.

Peter Boothe
fonte
Bom ponto para três maneiras de relaxar o problema! Eu acho que algoritmos aleatórios se enquadram na categoria "eficiente e inexata e geral".
Hsien-Chih Chang,
Verdade? Nem todos os algoritmos aleatórios são inexatos.
Jeffε
E é claro que você está certo, JeffE. Além disso, eu entendo que você está (ou estava) instruindo um ex-aluno meu em algoritmos! Quanto ao argumento de Hsien-Chih, não acho que algoritmos aleatórios se encaixem bem nesse esquema. Certamente, alguns algoritmos aleatórios (algoritmos genéticos e redes neurais vêm à mente) são inexatos, mas eficientes e gerais, mas alguns algoritmos aleatórios são bem exatos - considere o algoritmo para verificar se um número é primo! É um algoritmo aleatório, mas estou bastante confiante de que ninguém jamais conseguiu uma implementação razoável.
quer
5

NP-compeuete

NP-compeuete, você tem alguma evidência para essa sua conjectura e deve começar a considerar uma abordagem alternativa (por exemplo, alterar o problema para que fique mais fácil).

NP-compeuete

NP-compeuete

P=NP3-SUMAT

NP-compeueteCeuEuQvocêE

Resumindo, caracterizando um problema, você pode usar técnicas comuns. Ao estudar a classe a que está relacionada, você pode pensar em um nível abstrato, sem se preocupar com as especificidades desse problema em particular, que é comum em matemática e ciências em geral. Trabalhar com classes em vez de membros individuais permite que você use técnicas conhecidas e, além disso, aplique suas idéias a um número maior de objetos, em vez de apenas um.

chazisop
fonte
2
Muitas pessoas resolvem problemas completos de NP na prática, mesmo que sejam difíceis de aproximar. No caso médio, muitos problemas acabam sendo muito mais fáceis, embora isso possa ser difícil de mostrar; é ainda mais difícil provar algo sobre algoritmos heurísticos que funcionam bem na prática. Sugiro ao arquiteto de software que pergunte a alguém se o problema é "realmente" difícil antes de desistir e mudar seu design.
Yuval Filmus
Não estou dizendo que o design precisa mudar. Usar um algoritmo heurístico ou de aproximação parece-me (falsamente?) Como mudar o problema ... pois sei que você está solicitando soluções menos precisas (são aceitáveis? Depende da aplicação!).
chazisop
3

Cada problema tem várias conexões com outros problemas. Além disso, existem relações entre um problema e classes de complexidade.

Portanto, classificar um problema como NPC geralmente nos fornece informações sobre outros problemas, bem como sobre classes de complexidade.

Por exemplo, considere o problema de isomorfismo gráfico (IG). No artigo a seguir:

Uwe Schöning, isomorfismo gráfico está na baixa hierarquia , Anais do 4º Simpósio Anual de Aspectos Teóricos da Ciência da Computação , 1987, 114-124; também: Journal of Computer and System Sciences, vol. 37 (1988), 312-323.

está provado que, se GI ∈ NPC, a hierarquia polinomial (PH) cai para seu segundo nível; o que será um grande avanço na teoria da complexidade estrutural.

MS Dousti
fonte
3

pppp

Radu GRIGore
fonte
1
Ouvi dizer que houve um tempo em que você provou que alguns problemas são NP-completos, você teria sua tese de doutorado. Isso é verdade?
Hsien-Chih Chang,
@ Hsien-ChihChang 張顯 之: Eu não posso comentar sobre isso, mas esses resultados certamente costumavam ser muito mais populares algumas décadas atrás. Hoje em dia, parece cada vez mais difícil publicar um artigo em que você "apenas" prove um resultado de dureza (com exceção de "problemas famosos", é claro), enquanto esse não teria sido um problema nos anos 70-80, a julgar pelo abundância desse tipo de papel durante esse período.
Anthony Labarre