Por que não existem algoritmos de aproximação para SAT e outros problemas de decisão?

Eu tenho um problema de decisão NP-completo. Dada uma instância do problema, eu gostaria de criar um algoritmo que produza SIM, se o problema for possível e, NÃO, caso contrário. (Obviamente, se o algoritmo não for ideal, ele cometerá erros.)

Não consigo encontrar algoritmos de aproximação para esses problemas. Eu estava procurando especificamente pelo SAT e encontrei na página da Wikipedia sobre o algoritmo de aproximação o seguinte: Outra limitação da abordagem é que ela se aplica apenas a problemas de otimização e não a problemas de decisão "puros", como a satisfação, embora muitas vezes seja possível .. .

Por que não definimos, por exemplo, a taxa de aproximação como algo proporcional ao número de erros que o algoritmo comete? Como realmente resolvemos os problemas de decisão de maneira gananciosa e subótima?

Os algoritmos de aproximação são apenas para problemas de otimização, não para problemas de decisão.

Por que não definimos a taxa de aproximação como a fração de erros que um algoritmo comete ao tentar resolver algum problema de decisão? Como "a razão de aproximação" é um termo com um significado padrão bem definido, que significa outra coisa, e seria confuso usar o mesmo termo para duas coisas diferentes.

OK, poderíamos definir alguma outra relação (vamos chamá-la de outra coisa - por exemplo, "a relação det") que quantifica o número de erros que um algoritmo comete, para algum problema de decisão? Bem, não está claro como fazer isso. Qual seria o denominador dessa fração? Ou, dito de outra maneira: haverá um número infinito de instâncias de problemas e, para algumas delas, o algoritmo dará a resposta certa e outras para a resposta errada; portanto, você terá uma proporção que é "algo dividido pelo infinito", e isso acaba sendo sem sentido ou não definido.

Como alternativa, poderíamos definir como a fração de erros dos erros do algoritmo, em instâncias de problemas do tamanho n . Então, poderíamos calcular o limite de r n como n → ∞ , se esse limite existir. Isso faria$r_n$$n$$r_n$$n \to \infty$seja bem definido (se o limite existir). No entanto, na maioria dos casos, isso pode não ser muito útil. Em particular, assume implicitamente uma distribuição uniforme nas instâncias de problemas. No entanto, no mundo real, a distribuição real nas instâncias de problemas pode não ser uniforme - geralmente está muito longe de ser uniforme. Consequentemente, o número que você obtém dessa maneira geralmente não é tão útil quanto você poderia esperar: geralmente dá uma impressão enganosa de quão bom é o algoritmo.

Para saber mais sobre como as pessoas lidam com a intratabilidade (dureza do NP), dê uma olhada em Lidando com o intratabilidade: problemas completos do NP .

O motivo pelo qual você não vê razões de aproximação nos problemas de tomada de decisão é que elas geralmente não fazem sentido no contexto das perguntas que normalmente são feitas sobre problemas de tomada de decisão. Em uma configuração de otimização, faz sentido porque é útil estar "próximo". Em muitos ambientes, isso não faz sentido. Não faz sentido ver com que frequência você está "próximo" em um problema discreto de logaritmo. Não faz sentido ver com que frequência você está "próximo" de encontrar um isômero de gráfico. E da mesma forma, na maioria dos problemas de tomada de decisão, não faz sentido estar "próximo" da decisão certa.

Agora, em implementações práticas, há muitos casos em que é útil saber qual parte dos problemas pode ser decidida "rapidamente" e qual parte não. No entanto, diferentemente da otimização, não existe uma maneira única de quantificar isso. Você pode fazer isso estatisticamente, como sugere, mas apenas se souber a distribuição estatística de suas entradas. Na maioria das vezes, as pessoas interessadas em problemas de decisão não têm a mesma sorte de ter essas distribuições.

Como um estudo de caso, considere o problema da parada. Sabe-se que o problema da parada é indecidível. É uma pena, porque é um problema realmente útil para resolver se você estiver criando um compilador. Na prática, no entanto, descobrimos que a maioria dos programas é realmente muito fácil de analisar a partir de uma perspectiva de problemas interrompidos. Os compiladores aproveitam isso para gerar código ideal nessas circunstâncias. No entanto, um compilador deve reconhecer que existe a possibilidade de um determinado bloco de código não ser decidido. Qualquer programa que dependa do código "provavelmente decidível" pode ter problemas.

No entanto, a métrica usada pelos compiladores para determinar o desempenho deles na resolução desses casos particulares do problema de parada é muito diferente de uma métrica usada por um programa de criptografia para testar se um par específico de números primos é aceitavelmente reforçado contra ataques. Não existe um tamanho único para todas as soluções. Se você deseja uma métrica desse tipo, convém adaptá-la para se ajustar ao espaço de problemas e à lógica de negócios específicos.

Além das respostas existentes, deixe-me salientar que há situações em que faz sentido ter uma solução aproximada para um problema de decisão, mas funciona diferente do que você imagina.

Com esses algoritmos, apenas um dos dois resultados é determinado com certeza, enquanto o outro pode estar incorreto. Faça o teste de Miller-Rabin para números primos , por exemplo: Se o teste determinar que um número não é primo, esse resultado é certo. Mas, no outro caso, significa apenas que o número é provavelmente primo. Dependendo de quanto tempo de computação você está disposto a investir, você pode aumentar sua confiança no resultado, mas não será 100%, como é o caso não primo.

Isso é especialmente poderoso ao lidar com problemas indecidíveis: você pode escrever uma ferramenta que tente resolver o problema de parada de um pedaço de código específico. Se conseguir encontrar uma prova de que o programa não será repetido indefinidamente, você pode reivindicá-lo com 100% de certeza. Se você não conseguir encontrar essa prova, pode ser que o fluxo de controle do programa esteja muito complicado para a sua ferramenta analisar, mas não é uma prova de que ele funcionará para sempre. Ao simplificar as estruturas de controle, você poderá criar um programa equivalente suficientemente simples para a ferramenta provar que ela será interrompida por certo.