A 'direcionalidade' das reduções?

Estou me sentindo um pouco confuso com a direção das reduções usadas para mostrar que certos idiomas não são recursivos. Por exemplo, digamos que queremos determinar se o problema de parada ( $HALT_{TM}$ ) é indecidível. Eu sei que podemos assumir que é decidível e tentar construir uma decisão para o problema de aceitação, o que é impossível. Mas, embora estejamos usando o problema de aceitação ( $A_{TM}$ ) para ajudar a resolver a decidibilidade do problema de parada, reduzimos o problema de aceitação ao problema de parada, e não o contrário, certo?

Às vezes fico um pouco confuso quando encontro perguntas que me pedem para implantar uma redução; Me pedem para reduzir o idioma $x$ para $y$ , mas o que isso significa é que $y$ é uma instância mais simples de um problema de $x$ , certo (ou pelo menos deveria ser)? Estou assumindo que é impossível reduzir uma versão mais simples de um problema para uma versão mais complexa de um problema, estou certo em acreditar nisso?

computability turing-machines reductions halting-problem Chris T
fonte

Se acreditamos que é difícil construir uma escada para a lua, também devemos acreditar que é pelo menos tão difícil construir um dispositivo que duplica qualquer objeto - já que, se esse dispositivo fosse fácil de construir, poderíamos colocar um escada regular nela, conecte as duas escadas resultantes juntas para produzir uma escada de altura dupla e repita esse processo algumas vezes e, assim, resolva facilmente o problema que considerávamos difícil. Aqui, reduzi o problema de construir uma escada lunar ao problema de construir um duplicador de objetos para mostrar que o último é pelo menos tão difícil quanto o anterior.

Jrandom_hacker

@j_random_hacker Essa analogia parece bastante complicada e rapidamente se quebra. Eu poderia usar uma fábrica de escadas comum para obter minhas escadas (portanto, não é necessário um duplicador) e, depois de juntar algumas escadas, toda a construção ficará tão frágil que entrará em colapso devido ao seu próprio peso (por isso, duplicador não é suficiente).

David Richerby

@DavidRicherby: Concedido que as considerações estruturais são um grande problema, não há argumento :) Ignorá-las, porém, o fato de uma fábrica de escadas ser suficiente não é um problema: mostrar o problema A é pelo menos tão difícil quanto o problema B é suficiente para mostrar todas as instâncias de B podem ser resolvidas transformando-se em instâncias de A e, assim, resolvendo A também resolve B; a existência de outras soluções para B é irrelevante. (De fato, o fato de um duplicador de objetos poder ser usado para implementar uma fábrica de escadas significa que o problema do "duplicador" é pelo menos tão difícil quanto o problema da "fábrica de escadas", que parece uma conclusão válida!)

psmears

Possível duplicata de Quando o problema A se reduz ao problema B, qual é o problema mais complexo?

Kevin

@ DavidRicherby: Ao escrever "para a lua", acho que chamei a atenção para a parte mais frágil da analogia (a saber, a fragilidade das escadas). E sem espaço para definir "difícil", eu queria uma técnica que necessitasse de "uma quantidade linear de trabalho" ou pior (como sua fábrica de escadas) para se qualificar como "difícil" e "uma quantidade logarítmica de trabalho" (como minha duplicadora) para qualifique como "fácil". Talvez essa analogia não funcione, mas acho que algum tipo de analogia um pouco precisa e realista deve ser possível e útil.

Jrandom_hacker

Respostas:

Não se preocupe - todo mundo fica confuso com a direção das reduções. Mesmo as pessoas que trabalham com algoritmos e complexidade há décadas ocasionalmente têm um "Espere, deveríamos estar reduzindo $A$ para $B$ ou $B$ para $A$ ?" momento.

Reduzindo $A$ para $B$ produz uma declaração do formulário "Se eu pudesse resolver $B$ , então eu também saberia como resolver $A$ "." Resolver "nesse sentido pode significar" calcular usando qualquer máquina de Turing "ou" calcular em tempo polinomial "ou qualquer outra noção de solução que seu contexto exija.

Isso pode parecer contra-intuitivo, pois " $A$ reduz a $B$ "implica que resolver $B$ é pelo menos tão difícil quanto resolver $A$ , então você não reduziu a dificuldade. No entanto, você pode pensar nisso como reduzir o número de problemas que precisa resolver. Imagine que, no início do dia, seus objetivos fossem encontrar um algoritmo para $A$ e um algoritmo para $B$ . Bem, agora que você encontrou uma redução de $A$ para $B$ , você reduziu seus objetivos a apenas encontrar um algoritmo para $B$ .

David Richerby
fonte

"" Se eu pudesse resolver B, também saberia como resolver A "" - Além disso, se você sabe que resolver A é difícil, também sabe que resolver B é pelo menos tão difícil.

G. Bach

Um físico e um matemático foram convidados a remover duas unhas, uma delas perfurada na parede e a outra metade. O físico pegou primeiro o que estava no meio do caminho e, depois de trabalhar um pouco, conseguiu tirar o segundo. O matemático começou com o que estava na parede, pois era mais interessante. Depois de um tempo e esforço consideráveis, ele conseguiu divulgá-lo. Então ele olhou para o outro, e proferiu as palavras: "Isso pode ser simplificado para um caso já resolvido", ele deu um soco na parede.

Curinga

Não. Quando $A$ reduz a $B$ , significa intuitivamente que $A$ é mais simples que $B$ , Não o contrário.

Mais praticamente: suponha que você queira verificar $x \in A$ . Em vez de fazer isso de alguma maneira, você transforma $x$ de acordo com algumas funções (redução) $y=f(x)$ . Agora você precisa verificar $y \in B$ .

Você ainda não resolveu o problema inicial $x \in A$ , pois agora você tem outro problema a resolver: $y \in B$ . Isso significa que você reduziu o problema inicial para outro.

Pode parecer contra-intuitivo a princípio que reduzimos as coisas fáceis às mais complexas. De fato, pragmaticamente, por que alguém quer resolver uma tarefa fácil, reduzindo se a uma tarefa mais difícil? Não gostaríamos de reduzir nossa tarefa a uma tarefa ainda mais fácil?

No entanto, a verdade é: se pudéssemos resolver uma tarefa difícil $A$ reduzindo-o a uma tarefa fácil $B$ , Isso significa que $A$ não foi realmente mais difícil do que $B$ . De fato, se resolver $A$ pode ser alcançado aplicando a função de redução e resolvendo o problema "mais fácil" $B$ , significa que $A$ foi mais fácil do que $B$ em primeiro lugar.

chi
fonte

Uma redução de $A$ para $B$ é algo que faz parte do trabalho necessário para fazer $A$ e o que falta fazer é $B$ . Por exemplo, "obter comida" pode ser reduzido a "cozinhar" por "obter ingredientes". Isso significa que "cozinhar" é mais difícil do que "obter comida": qualquer pessoa que possa "cozinhar" pode "obter comida" (assumindo que a redução de "obter ingredientes" sempre funcione, por exemplo, na presença de um local que dê ingredientes de graça) .

Desenhar coisas tende a torná-las mais fáceis de entender:

Você deseja construir a caixa azul (que representa um algoritmo que recebe uma entrada $x$ e decide se $x\in A$ ) A redução é então a caixa vermelha e, quando você a tiver, a única coisa que resta fazer para construir a caixa azul é construir a caixa verde. Então, se você tem uma caixa vermelha (que reduz $A$ para $B$ ), construindo a caixa verde (que decide $B$ ) é pelo menos tão difícil quanto construir o azul (que decide $A$ ): Se você tiver uma caixa verde, é muito fácil criar uma azul, enquanto que se você construir uma caixa azul, poderá não conseguir construir uma caixa verde.

Observe que as razões para as duas condições que definem uma redução aparecem neste desenho: o fato de que $f$ é computável significa que você pode construir a caixa vermelha, enquanto o fato de que $f(x)\in B\iff x \in A$ significa que você pode conectar os dois fios mais à direita.

xavierm02
fonte

Acho o primeiro parágrafo bastante difícil de seguir (novamente, não tenho certeza de que a analogia seja muito esclarecedora), mas um +1 definitivo para o restante da resposta.

David Richerby