Quais são as técnicas comuns para reduzir problemas entre si?

40

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 2L1L2L2L1L1L2

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!

Rafael
fonte
Veja aqui algumas reflexões sobre como encontrar parceiros adequados e idéias para reduções.
Raphael

Respostas:

18

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.L1RL2RL1L2

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.L2L1L2R

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

f(A,k)=(A,(1,,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)vVWw

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.φkkφk

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

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

f(A)={(A,12aAa),aAamod2=0(A,1+aA|a|),else

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.AA k k(A,k)Akk

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 kGs,tGkstGk

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 Gf(G)=(G,v,v,n)vG

Rafael
fonte
2
Aqui está um exemplo chamado de problema do comprador em viagem (TPP) que tem muitos problemas difíceis como seu caso especial.
21413 Juho
Outro exemplo da computabilidade é o problema de parada especial (que geralmente é diretamente indecidível), um caso especial do problema geral de parada.
Raphael
O KNAPSACK é realmente uma redução correta do SUBSET-SUM? KNAPSACK pede valor SUBSET-SUM pede valor exato, não? Por exemplo, uma instância SUBSET-SUM seria uma instância 'não' (não consigo obter exatamente 4 de apenas um item com o valor 5), mas sua redução no KNAPSACK reduziria isso para e , então seria uma instância de 'sim' lá ... Ou estou perdendo alguma coisa? { 5 } , 4 { 5 } , { 1 } , 4 , 1 5 > 4>=v{5},4{5},{1},4,15>4
johnny
15

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

DOUBLE-SAT={φφ is a boolean formula with at least 2 satisfying assignments }

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) .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.NP

sab φ v ( v ¬ v ) φ v = v = φ φ vNP -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 .SATφv(v¬v)φv=⊥v=φφv

Segue-se que é -completo, que é o que queríamos mostrar.N PDOUBLE-SATNP

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.

Juho
fonte
6

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çaL

MKfML

com o problema de interrupção (ou qualquer outro idioma / problema indecidível).K={MM(M) 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 MMfMfM

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, :¯ KLK¯


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

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).AB ABBA

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.

vzn
fonte
2
Gostaria de saber se você notou a nota de rodapé na pergunta. Eu acho que as respostas devem ser mais específicas e mostrar como um método específico é aplicado. Isso parece bastante vago e geral. Como melhoria, que tal mostrar como os gadgets podem ser construídos e usados?
21413 Juho
2
Além disso: você pode explicar por que algo depende das classes de complexidade envolvidas e como. Além disso, e se eu quiser ir de para ou para , o que devo fazer então? E o "problema mais próximo" - você poderia dar um exemplo de um par de problemas? B B AABBA
21413 Juho
o powerpoint mostra dois exemplos de gadgets sendo usados. um exemplo de um problema mais próximo: suponha que alguém tenha um problema relacionado à teoria dos números. há uma seção de G&J relacionada à teoria dos números. etcetera. quanto a outras classes de complexidade fora do NP, existem muitas, mas as listas de problemas não são tão completas ou prontamente obtidas. Portanto, em outras palavras, para restringir a pergunta original, talvez ela deva ser limitada a reduções completas de NP ...?
fácil
2
Eu recomendo adicionar todas as informações à resposta, pois os comentários podem ser excluídos a qualquer momento. O link para os slides também pode ser interrompido amanhã. O que eu estava lidando com o problema próximo: o que faço exatamente quando encontro um problema parecido (suponha que eu seja um iniciante)?
Juho