Na teoria da computabilidade e da complexidade (e talvez em outros campos), as reduções são onipresentes. Existem muitos tipos, mas o princípio permanece o mesmo: mostre que um problema é pelo menos tão difícil quanto outro problema mapeando instâncias de para instâncias a solução em . Essencialmente, mostramos que qualquer solucionador para também pode resolver se permitirmos usar a função de redução como pré-processador.L 2 L 2 L 1 L 1 L $L_1$$L_2$$L_2$$L_1$$L_1$$L_2$

Realizei minha parcela de reduções ao longo dos anos e algo continua me incomodando. Embora toda nova redução exija uma construção criativa (mais ou menos), a tarefa pode parecer repetitiva. Existe um conjunto de métodos canônicos?

Quais são as técnicas, padrões e truques que podemos usar regularmente para construir funções de redução?

^{Isso deveria se tornar uma pergunta de referência . Portanto, tenha o cuidado de fornecer respostas gerais, apresentadas didaticamente, ilustradas por pelo menos um exemplo, mas que abranjam muitas situações. Obrigado!}

O caso especial

Suponha que queremos mostrar com relação a alguma noção de redução de R . Se L 1 é um caso especial de L 2 , isso é bastante trivial: podemos essencialmente usar a função de identidade. A intuição por trás disso é clara: o caso geral é pelo menos tão difícil quanto o caso especial.$L_1 \leq_R L_2$$R$$L_1$$L_2$

Na "prática", recebemos e estamos presos ao problema de escolher um bom parceiro de redução L 1 , ou seja, encontrar um caso especial de L 2 que provou ser R- duro.$L_2$$L_1$$L_2$$R$

Exemplo Simples

Suponha que queremos mostrar que o KNAPSACK é difícil de usar NP. Felizmente, sabemos que SUBSET-SUM é NP-completo, e é realmente um caso especial de KNAPSACK. A redução

$\qquad f(A,k) = (A, (1,\dots,1), k, |A|)$

é suficiente; é a instância do KNAPSACK que pergunta se podemos alcançar pelo menos o valor v com os valores do item em V para que os pesos correspondentes de W permaneçam abaixo de w no total. Não precisamos das restrições de peso para simular SUBSET-SUM; portanto, apenas as definimos com valores tautológicos.$(V,W,v,w)$$v$$V$$W$$w$

Problema de exercício simples

Considere o problema MAX-3SAT: dada uma fórmula proposicional e um número inteiro k , decida se existe uma interpretação de que preencha pelo menos cláusulas. Mostre que é NP-difícil.$\varphi$$k$$\varphi$$k$

3SAT é um caso especial; com o número de cláusulas em é suficiente.m $f(\varphi) = (\varphi, m)$$m$$\varphi$

Exemplo

Suponha que estamos investigando o problema SUBSET-SUM e queremos mostrar que é difícil para o NP.

Temos sorte e sabemos que o problema da PARTIÇÃO é NP-completo. Confirmamos que é realmente um caso especial de SUBSET-SUM e formulamos

$\qquad \displaystyle f(A) = \begin{cases} \left(A, \frac{1}{2}\sum_{a \in A} a\right) &, \sum_{a \in A} a\mod 2 = 0 \\ \left(A, 1 + \sum_{a \in A} |a|\right) &, \text{else} \end{cases}$

onde é o conjunto de entrada de PARTITION e é uma instância para SUBSET-SUM que solicita um subconjunto de somando . Aqui, temos que cuidar do caso em que não há ajuste ; nesse caso, damos uma instância arbitrária inviável.$A$A k $(A,k)$$A$$k$$k$

Problema do exercício

Considere o problema LONGEST-PATH: dado um gráfico direcionado , nós de e número , decida se existe um caminho simples de a em de comprimento pelo menos .s , t G k s t G $G$$s,t$$G$$k$$s$$t$$G$$k$

Mostre que LONGEST-PATH é NP-difícil.

O CICLO DE HAMILTON é um problema bem conhecido de NP-completo e um caso especial de CAMINHO MAIS LONGO; para o nó arbitrário em é suficiente. Observe em particular como a redução do HAMILTON-PATH requer mais trabalho.v $f(G) = (G,v,v,n)$$v$$G$

Aproveitando um problema conhecido nas proximidades

Quando se depara com um problema que parece difícil, geralmente é uma boa ideia tentar procurar um problema semelhante que já está comprovadamente difícil. Ou talvez você possa ver imediatamente que um problema é muito semelhante a um problema conhecido.

Problema de exemplo

Considere um problema

desejamos mostrar que completo. Observamos rapidamente que está muito próximo de um problema que já sabemos que é difícil, a saber, o problema de satisfação (SAT) .$\mathsf{NP}$

A associação a é fácil de mostrar. O certificado é duas atribuições. Claramente, pode ser verificado em tempo polinomial se as atribuições satisfazem uma fórmula.$\mathsf{NP}$

sab φ v ( v ∨ ¬ v ) φ v = ⊥ v = ⊤ φ φ $\mathsf{NP}$ -dureza segue de uma redução de . Dada uma fórmula , nós a modificamos introduzindo uma nova variável . Nós adicionamos uma nova cláusula à fórmula. Agora, se for satisfatório, será satisfatório com e . Portanto, tem pelo menos 2 tarefas satisfatórias. Por outro lado, se não for satisfatório, ele definitivamente não se tornará satisfatório, independentemente do valor de .$\text{SAT}$$\varphi$$v$$(v \vee \neg v)$$\varphi$$v = \perp$$v = \top$$\varphi$$\varphi$$v$

Segue-se que é -completo, que é o que queríamos mostrar.N $\text{DOUBLE-SAT}$$\mathsf{NP}$

Localizando problemas próximos

Reduzir problemas é uma espécie de arte, e muitas vezes é necessária experiência e criatividade. Felizmente, muitos problemas difíceis já são conhecidos . Os computadores e a intratabilidade de Garey e Johnson: um guia para a teoria da completude da NP é clássico, com seu apêndice listando muitos problemas. O Google Scholar também é um amigo.

Em computabilidade, frequentemente investigamos conjuntos de máquinas de Turing. Ou seja, nossos objetos são funções e temos acesso a uma numeração de Gödel . Isso é ótimo porque podemos fazer praticamente o que queremos com a função de entrada, desde que continuemos computáveis.

Suponha que queremos mostrar que não é decidível. Nosso objetivo é chegar à equivalência de desgraça$L$

$\qquad \langle M \rangle \in K \iff \langle f_M \rangle \in L$

com o problema de interrupção (ou qualquer outro idioma / problema indecidível).$K = \{ \langle M \rangle \mid M(\langle M \rangle) \text{ halts} \}$

Portanto, precisamos criar um mapeamento computável para que seja sempre computável. Este é um ato criativo informado pela equivalência da desgraça. Veja alguns exemplos para ter uma idéia de como isso funciona:f $\langle M \rangle \mapsto \langle f_M \rangle$$f_M$

• Mapeando Reduções para Complementar$A_{\mathrm{TM}}$
• É possível mapear reduzir um desses idiomas para o outro?

O mesmo funciona para mostrar que não é semi-decidível escolhendo idiomas não-semi-decidíveis como parceiro de redução, por exemplo, :¯ $L$$\overline{K}$

• A regularidade do idioma aceito por uma determinada máquina de Turing é uma propriedade semi-decidível?
• O conjunto de funções constantes computáveis ​​é recursivamente enumerável?

1. É aqui que a numeração de Gödel entra: obtemos a computabilidade desse mapeamento (geralmente) de graça.

depende das classes de complexidade envolvidos, e se alguém quiser reduzir a partir de uma determinada a um desconhecido , ou um desconhecido para uma dada . o cenário comum é provar os problemas NP Hard ou NP Complete. Uma técnica comum é construir "gadgets" em um domínio que se comportam de uma certa maneira, imitando o comportamento de outro domínio. por exemplo, para converter SAT em capa de vértice, constrói-se "gadgets" na capa de vértice que se comportam de maneira semelhante às cláusulas de SAT, por exemplo, na seguinte apresentação de slides: NP Reduções completas por Krishnamoorthy (também com um exemplo para o caminho de Hamilton).$A$B $B$$B$$A$

Uma estratégia útil é trabalhar com grandes compilações de problemas da classe de complexidade em questão e encontrar os "problemas aparentes mais próximos" do problema que está sendo estudado. uma excelente referência nesse sentido é Computers and Intratability, um guia para a teoria da completude de NP, Garey e Johnson organizados por diferentes tipos de problemas.