Por que os problemas NP-completos não têm taxas de aproximação semelhantes?

Como 2 problemas completos de NP são por definição redutíveis um ao outro, portanto, uma solução para um deles pode ser obtida usando uma caixa preta para resolver o outro, por que eles não têm taxas de aproximação semelhantes (consultando as contrapartes de otimização) )? Eu acho que algum desvio constante ou mesmo polinomial pode ser entendido, mas temos o caso de algoritmos de aproximação de fator constante para alguns problemas NP-completos e, por outro lado, outros problemas que não podem ser sequer aproximados por um algoritmo de aproximação de razão polinomial , como TSP geral? Obrigado

cc.complexity-theory approximation-algorithms reductions N27
fonte

porque as reduções da caixa preta preservam apenas o aspecto SIM / NÃO dos problemas (de decisão), não a proximidade das aproximações.

Suresh Venkat

se eu reduzir 3SAT para cobertura de vértice, a cobertura de vértice de tamanho k implica satisfação e vice-versa. Mas se eu receber uma cobertura de vértice de tamanho 2k, isso não significa que posso satisfazer metade das cláusulas.

Suresh Venkat

Escolha uma redução específica de um problema NP-completo para outro e tente estendê-lo para preservar as taxas de aproximação. Você verá o que está errado.

Peter Shor

A resposta de Peter é realmente a melhor. Apenas tente e veja o que acontece. Eu acho que por ceticismo filosófico você quer dizer 'eu realmente não entendo'. Às vezes, a melhor maneira é tentar alguns exemplos e deixar a intuição crescer.

Suresh Venkat

\log | C |

$\log |C|$

| C |

$|C|$

| C |^{2}

$|C|^2$

2^{| C |}

$2^{|C|}$

C

$C$

Jukka Suomela

Respostas:

As reduções são definidas com relação à versão de decisão dos problemas. As proporções de aproximação para suas versões de otimização são uma questão separada, que parece relacionada, mas não necessariamente precisa ser. Então, para responder sua pergunta com uma pergunta, de uma perspectiva filosófica, por que você deve esperar que o NPC da classe preserve relações de aproximação quando não está definido em relação a eles em primeiro lugar?

Lev Reyzin
fonte

"Reduções são definidas com relação à versão de decisão dos problemas." Isso é verdade, dizem reduções de Levin ?

MS Dousti

Você está certo, nem todas as reduções são definidas por versões de decisão erradas, mas podemos definir o NPC apenas em termos de reduções de caixa preta, e acho que isso pode levar a debates sobre como essas classes mudam com a redução usada ... Eu deveria ter dito "a classe NPC é definida para problemas de decisão". Não é realmente um argumento preciso, pois podemos até definir uma classe de problemas de decisão cujas versões de otimização preservam proporções de aproximação, mas não é isso que fazemos para o NPC da classe. Acho que dada a pergunta de @ N27 é uma objeção filosófica, posso dar uma resposta filosófica. :)

Lev Reyzin