Por que os problemas NP-completos são tão diferentes em termos de aproximação?

22

Gostaria de começar a pergunta dizendo que sou programador e não tenho muita experiência em teoria da complexidade.

Uma coisa que eu notei é que, embora muitos problemas sejam NP-completos, quando estendidos a problemas de otimização, alguns são muito mais difíceis de aproximar do que outros.

Um bom exemplo é o TSP. Embora todos os tipos de TSP sejam NP-completos, os problemas de otimização correspondentes ficam cada vez mais fáceis de serem aproximados com sucessivas simplificações. O caso geral é completo com NPO, o caso métrico é completo com APX e o caso euclidiano realmente possui um PTAS.

Isso parece contra-intuitivo para mim, e estou me perguntando se existe uma razão para isso.

GregRos
fonte
2
Se você quiser ler o básico, consulte nossa pergunta de referência . Quanto à sua pergunta, você está observando a diferença entre problemas fracos e fortes de NP-completos.
Raphael

Respostas:

14

Uma razão pela qual vemos complexidades de aproximação diferentes para problemas de NP-completo é que as condições necessárias para NP-completo constituem uma medida granular muito grossa da complexidade de um problema. Você pode estar familiarizado com a definição básica de um problema sendo NP-complete:Π

  1. Π está em NP e
  2. Para todos os outros problemas no NP, podemos transformar uma instância de em uma instância de em tempo polinomial, de modo que seja uma instância sim de se e somente se for uma instância sim de .ΞxΞyΠyΠxΞ

Considere a condição 2: tudo o que é necessário é que possamos pegar e transformá-lo em algum que preserva a resposta sim / não "de bit único". Não há condições sobre, por exemplo, o tamanho relativo das testemunhas para sim ou não (ou seja, o tamanho da solução no contexto de otimização). Portanto, a única medida usada é o tamanho total da entrada, que apenas fornece uma condição muito fraca para o tamanho da solução. Portanto, é bastante "fácil" transformar um em um .xyΞΠ

Podemos ver a diferença em vários problemas NP-completos, observando a complexidade de alguns algoritmos simples. -Coloring tem uma força bruta (onde é o tamanho da entrada). Para -Dominating Set, uma abordagem de força bruta assume . Estes são, em essência, os melhores algoritmos exatos que temos. -Vertex Cover, no entanto, possui um algoritmo simples (escolha uma aresta, ramo no qual o nó de extremidade incluir, marque todas as áreas cobertas, continue até você não ter arestas desmarcadas ou pressionar seu orçamento dekO(kn)nkO(nk)kO(2knc)ke bactrack). Sob reduções de um-tempo em tempo polinomial (reduções de Karp, ou seja, o que estamos fazendo na condição 2 acima), esses problemas são equivalentes.

Quando começamos a abordar a complexidade com ferramentas ainda um pouco mais delicadas (complexidade de aproximação, complexidade parametrizada, outras que não consigo pensar), as reduções que usamos se tornam mais estritas, ou melhor, mais sensíveis à estrutura da solução, e as diferenças começam a aparecer; -Vertex Cover (como Yuval mencionou) tem uma aproximação 2 simples (mas não possui um FPTAS, a menos que algumas classes de complexidade colapsem ), -Dominating Set possui um algoritmo de aproximação (mas não -proximação para alguns ), e aproximação realmente não faz sentido para a versão direta do -Coloring.kk(1+logn)(clogn)c>0k

Luke Mathieson
fonte
13

Uma maneira de considerar a diferença entre versão de decisão e versão de otimização é considerar diferentes versões de otimização da mesma versão de decisão. Tomemos, por exemplo, o problema MAX-CLIQUE, que é muito difícil de aproximar em termos do parâmetro usual - o tamanho da clique. Se alterarmos o parâmetro de otimização para o logaritmo do tamanho do clique, obteremos um problema com o algoritmo de aproximação . Se alterarmos o parâmetro de otimização para , onde é o tamanho do clique, então podemos obter um algoritmo de aproximação .1 / 2 + k / n K O ( 1 )O(logn)1/2+k/nkO(1)

Esses exemplos não são completamente inventados. Os problemas de MAX-INDEPENDENT-SET (equivalente a MAX-CLIQUE) e MIN-VERTEX-COVER estão intimamente relacionados - o complemento de um conjunto independente é uma cobertura de vértice. Mas enquanto o primeiro é difícil de aproximar, o segundo tem uma simples aproximação 2.

Às vezes, reduções que mostram a dureza NP de um determinado problema também podem mostrar dureza de aproximação, mas esse nem sempre é o caso - depende da redução. Por exemplo, a redução de MAX-INDEPENDENT-SET para MIN-VERTEX-COVER não implica dureza na aproximação do último problema, que é muito mais fácil de aproximar do que o anterior.

Resumindo, a dureza NP é apenas um aspecto de um problema. A dureza da aproximação é um aspecto diferente e depende fortemente da noção de aproximação.

Yuval Filmus
fonte
Você concorda com a afirmação intuitiva de Luke Mathieson de que as reduções de karp são inerentemente menos "delicadas" do que as usadas nas classes de complexidade de aproximação? Caso contrário, você tem bons exemplos (talvez em outras classes de complexidade como EXP) contra essa ideia?
GregRos
Esta não é uma afirmação intuitiva. Supondo você pode provar que, em alguns casos, existe uma redução de Karp, mas uma redução de preservação de aproximação não existe. Isso acontece, por exemplo, no caso de conjuntos independentes e cobertura de vértices: há uma redução de Karp, mas não uma redução de preservação de aproximação, a menos que . P = N PPNPP=NP
Yuval Filmus
5

Como uma abordagem intuitiva, considere que as instanciações de problemas de NP completos nem sempre são tão difíceis quanto no caso geral. A satisfação binária (SAT) é NP-completa, mas é trivial encontrar a solução para A v B v C v D v ... Os algoritmos de complexidade apenas ligam o pior caso, não o caso médio, ou mesmo o caso de 90% .

A maneira mais fácil de reduzir um problema de NP completo para algo mais simples é simplesmente excluir as partes duras. Está trapaceando, sim. Mas muitas vezes as partes restantes ainda são úteis para resolver problemas do mundo real. Em alguns casos, é fácil traçar a linha entre "fácil" e "difícil". Como você apontou para o TSP, há uma forte redução de dificuldade à medida que você restringe o problema às direções "normais" em que se pode pensar. , é mais difícil encontrar maneiras úteis da vida real de segregar as partes fáceis e difíceis.

Para deixar totalmente o domínio do CS e da matemática, considere um carro velho. Seu amigo quer dirigir. Se você tiver que dizer a ele: "ei, o carro funciona perfeitamente. Só não suba a mais de 100 km / h. Há uma oscilação desagradável que o derrubará da estrada", provavelmente não é grande coisa. Seu amigo provavelmente só queria passear pela cidade de qualquer maneira. No entanto, se você precisar dizer a ele, "você precisa apertar a embreagem para passar do 1º ao 2º, ou o motor irá parar", pode ser mais difícil para seu amigo usar o carro pela cidade sem um treinamento menor.

Da mesma forma, se um problema de NP completo ficar difícil apenas em casos exóticos, ele reduzirá a complexidade rapidamente quando você olha para subdomínios. No entanto, se ficar difícil em casos comuns, não existem muitos subdomínios úteis que evitam a parte difícil.

Cort Ammon - Restabelecer Monica
fonte
Entendo o que você está dizendo e é uma perspectiva interessante. É interessante que, diferentemente da simplificação de 3-SAT para 2-SAT, a simplificação de TSP para TSP métrico seja "forte o suficiente" para transformar um problema completo de NPO em um problema completo de APX, mas não "forte o suficiente" para afetam a rastreabilidade do problema de decisão. A meu ver, essa "hierarquia" de simplificações faz com que faça ainda menos sentido. P=NP
GregRos