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

Estou correto ao entender que provar que um NP está completo é um sucesso de pesquisa? Se sim, por quê?

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.

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.

$NP-complete$

$NP-complete$, 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-complete$

$NP-complete$

$P=NP$$3-SAT$

$NP-complete$$CLIQUE$

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.

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.

$p$$p$$p$$p$