Pergunta simples sobre problemas de decisão

8

(Estou no meio do meu primeiro curso teórico de cs, então peço desculpas antecipadamente pelo que provavelmente é uma pergunta estúpida.)

Então, dizemos que alguma linguagem L está em P, o que significa que uma máquina de Turing pode ser construída que gera 1 se x estiver em L e 0, caso contrário; Além disso, a máquina é executada em tempo polinomial. Eu entendo isso.

Mas muitas pessoas dizem que existem certos problemas em P que não me parecem problemas de decisão; por exemplo, maximizar uma função sujeita a restrições lineares. O que significa que "programação linear" está em P? Certamente "encontrar o valor máximo" não é um problema de decisão?

cc.complexity-theory Xodarap
fonte

Respostas:

16

Você está certo: formalmente, P inclui apenas problemas de decisão. Porém, muitos problemas de decisão têm problemas de otimização correspondentes: encontre o tamanho da maior correspondência em um gráfico, encontre o comprimento do caminho mais curto de s a t em um gráfico, etc.

Geralmente, eles podem ser reduzidos a problemas de decisão, perguntando: "O gráfico possui uma correspondência usando mais de k arestas?" ou "Existe um caminho s-> t de comprimento menor que k?"

Obviamente, se você puder resolver o problema de otimização, poderá resolver o problema de decisão. O inverso também costuma ser verdadeiro, até fatores logarítmicos. Se você quiser saber o tamanho da maior correspondência em um gráfico, por exemplo, poderá fazer chamadas repetidas para seu algoritmo para o problema de decisão "O gráfico possui uma correspondência usando mais de k arestas?" e faça uma pesquisa binária no valor "k". Dessa forma, você precisará no máximo de chamadas de log (m), em que m é o número de arestas. Para a maioria dos problemas, há uma redução análoga.

Aaron Roth
fonte
Para acompanhar a resposta de Aaron, a programação linear pode ser formulada como um problema de decisão, especificando alguns limites, k, nos quais você está interessado; esse é um truque comum. Por exemplo, existe uma atribuição de valores para variáveis ​​da função objetivo de forma que você satisfaça todas as restrições lineares E de modo que a função objetivo tenha um valor maior ou igual (resp., Menor que ou igual a) k? Você pode, por exemplo, decidir isso em tempo polinomial maximizando / minimizando a função objetivo.
Daniel Apon
Então, essencialmente, se você sabe "existe uma solução para o X?" está em P, então geralmente (mas nem sempre) o problema " qual é a solução para o X?" será solucionável em tempo polinomial?
Xodarap 28/09
3
Xodarap: isso mesmo. Geralmente, a capacidade de resolver o problema de decisão rapidamente permite resolver o problema de pesquisa rapidamente, mas nem sempre. Como um famoso contra-exemplo: pelo teorema de Nash, todo jogo de matriz tem um equilíbrio misto de Nash, então resolver o problema de decisão "Esse jogo tem um equilíbrio de Nash" é trivial - a resposta é sim. Pensa-se, porém, que é difícil encontrar um equilíbrio de Nash em um jogo genérico.
Aaron Roth
outro exemplo disso é o teorema de Radon. Dado qualquer ponto d + 2 em R ^ d, existe uma partição dos pontos em dois conjuntos, de modo que os dois cascos convexos se cruzam. Fácil de verificar uma partição candidata, mas difícil de encontrar uma.
Suresh Venkat
11

Formalmente, a classe de funções que pode ser calculada em tempo polinomial é chamada FP . As pessoas costumam dizer "P" em vez de "FP", já que a distinção é apenas sintática e nenhuma confusão real acontecerá.

Noam
fonte
8

Uma pergunta muito semelhante já foi feita no tópico " Classe de complexidade do FNP ". Lá, o questionador perguntou essencialmente a diferença entre as classes de complexidade NP e FNP. Você está perguntando a diferença entre as classes de complexidade P e FP. Em resumo, P e NP são classes de decisão, enquanto as versões "F" (FP e FNP) são classes de função. Para mais informações, consulte o tópico citado acima.

MS Dousti
fonte
7

Problemas que exigem uma solução podem ser transformados em problemas de decisão, se houver alguma maneira de medir o quão boa é uma solução. A versão da decisão especifica que qualquer solução deve ser melhor que algum valor limite. Por exemplo, a versão de decisão do PROGRAMA LINEAR é obtida perguntando se o programa linear é viável.

András Salamon
fonte
Ah, na verdade eu não estou ciente disso - é decidir se existe alguma solução viável mais comum do que decidir se existe uma solução viável de um certo valor?
Daniel Apon
1
CX≥BXCB-CX≤-BCX≥B