Como faço para construir reduções entre problemas para provar que um problema é NP-completo?

Estou fazendo um curso de complexidade e estou tendo problemas para apresentar reduções entre os problemas dos NPCs. Como posso encontrar reduções entre problemas? Existe um truque geral que eu possa usar? Como devo abordar um problema que me pede para provar que é um NPC?

Não há nenhuma bala mágica; As provas de dureza NP são difíceis. No entanto, existe uma estrutura geral para todas essas provas. Muitos estudantes que lutam com as provas de dureza NP estão confusos sobre o que deveriam estar fazendo, o que obviamente torna impossível descobrir como fazê-lo. Então, aqui está o que fazer para provar um problema NP-difícil.

Primeiro, a menos que você esteja apenas fazendo a lição de casa, você precisa decidir qual problema NP-difícil reduzir ao seu problema . Isso é em grande parte uma questão de "cheiro". Se o número 3 aparecer em qualquer lugar da declaração do problema, tente reduzir de ou ou . (Sim, estou falando sério.) Se o seu problema envolve encontrar uma subsequência, permutação ou caminho ideal, tente reduzir de ou . Se o seu problema solicitar o menor subconjunto com uma determinada propriedade, tente ; se ele solicitar o maior subconjunto com uma determinada propriedade, tente$\mathsf{3SAT}$$\mathsf{3Color}$$\mathsf{3Partition}$$\mathsf{HamiltonianCycle}$$\mathsf{HamiltonianPath}$$\mathsf{Clique}$$\mathsf{IndependentSet}$. Se o seu problema envolver algo no plano, tente ou . E assim por diante. Se o seu problema não "cheira" a nada, ou é provavelmente a sua melhor aposta.$\mathsf{PlanarCircuitSAT}$$\mathsf{PlanarTSP}$$\mathsf{3SAT}$$\mathsf{CircuitSAT}$

Obviamente, você já precisa saber exatamente como todos esses problemas são definidos e, quanto mais simples o problema que você reduzir, melhor. Portanto, por mais legal que o resultado pareça, não recomendo reduzir de ou ou ou .$\mathsf{Minesweeper}$$\mathsf{Tetris}$$\mathsf{OneCheckersMove}$$\mathsf{SuperMarioBros}$

Segundo, a redução real. Para reduzir o problema X (o que você conhece é NP-difícil) para o problema Y (o que você está tentando provar é o NP-Hard, você precisa descrever um algoritmo que transforma uma instância arbitrária de X em uma instância legal de Y O algoritmo de redução precisa fazer algo específico com cada "recurso" da instância X. A parte da saída de cada "recurso" é geralmente chamada de gadget .

Mas o que é um recurso? Isso depende do problema X. Por exemplo:

• Para transformar uma instância de , você precisará de um gadget para cada variável e para cada cláusula na fórmula de entrada. Cada gadget variável deve ter dois "estados" que correspondem a "verdadeiro" e "falso". Cada dispositivo de cláusula também deve ter vários "estados", cada um dos quais de alguma forma força pelo menos um dos literais nessa cláusula a ser verdadeiro. (Os estados não fazem parte da saída do algoritmo de redução.)$\mathsf{3SAT}$

• Para transformar uma instância de , você precisará de um gadget para cada vértice e cada aresta do gráfico de entrada e outro gadget para definir as três cores.$\mathsf{3Color}$

• Para transformar uma instância de , você precisará de um gadget para cada entrada, para cada fio e para cada porta no circuito de entrada.$\mathsf{PlanarCircuitSat}$

A forma real do gadget depende problema Y, o que você está reduzindo a . Por exemplo, se você está reduzindo a um problema com gráficos, seus gadgets serão pequenos subgráficos; veja o artigo da Wikipedia. Se você estiver reduzindo um problema de agendamento, cada gadget será um conjunto de tarefas a serem agendadas. Se você está reduzindo a um problema sobre Mario , cada gadget será um conjunto de blocos e tijolos e Koopas.

Isso pode ficar confuso se os dois problemas envolverem o mesmo tipo de objeto. Por exemplo, se X e Y são problemas sobre gráficos, seu algoritmo transformará um gráfico (uma instância de X) em um gráfico diferente (uma instância de Y). Escolha sua notação com sabedoria, para não confundir esses dois gráficos. Também recomendo o uso de várias cores de tinta.

Por fim, seu algoritmo de redução deve satisfazer três propriedades:

• É executado em tempo polinomial. (Isso geralmente é fácil.)

• Se o seu algoritmo de redução receber uma instância positiva de X como entrada, ele produzirá uma instância positiva de Y como saída.

• Se o seu algoritmo de redução produz uma instância positiva de Y como saída, ele deve ter recebido uma instância positiva de X como entrada.

Há uma sutileza importante aqui. Seu algoritmo de redução funciona apenas em uma direção, das instâncias de X às instâncias de Y, mas provar que o algoritmo está correto requer um raciocínio sobre a transformação nas duas direções. Você também deve se lembrar que seu algoritmo de redução não pode dizer se uma determinada instância de X é positiva ou negativa - isso exigiria resolver um problema difícil de NP em tempo polinomial!

Esse é o que . O como apenas vem com a prática.

JeffE descreve a estratégia mais comum: conheça muitos problemas completos de NP, encontre um que se encaixe muito bem e faça a redução fácil .

Outra estratégia válida é sempre usar o 3SAT (ou qualquer outro problema). Isso pode tornar algumas reduções mais complexas, mas o lado positivo é que você tem muita experiência em expressar satisfação em outros tipos de problemas. Assim, você economiza o tempo de encontrar um bom parceiro de redução (incluindo becos sem saída) e espera que sua experiência permita que você faça a redução rapidamente, mesmo que seja mais difícil.

Essa abordagem também possui uma meta beleza: (3) o SAT é um dos poucos problemas para os quais a integridade do NP foi comprovada (quase) diretamente. Portanto, confiar apenas nessa prova mantém sua "árvore de provas" plana, evitando longas cadeias de reduções.