Versão de otimização de problemas de decisão

26

Sabe-se que cada problema de otimização / pesquisa tem um problema de decisão equivalente. Por exemplo, o problema do caminho mais curto

  • optimização / pesquisa versão: Dado um gráfico não ponderada não dirigida e dois vértices , encontrar o caminho mais curto entre e .L = ( V , E ) G=(V,E)v , u V v,uVv vuu
  • versão decisão: Dado um gráfico não ponderada não dirigida , dois vértices , e um número inteiro não negativo , existe um caminho em entre e , cujo comprimento é no máximo ?G = ( V , E ) G=(V,E)v , u V v,uVk kG Gu uv vkk

Em geral, "Encontre st !" torna-se "Existe x \ no X st f (x) \ leq k ?".x X xXf ( x ) = min { f ( x ) x X } f(x)=min{f(x)xX}x X xXf ( x ) kf(x)k

Mas o inverso também é verdadeiro, ou seja, existe um problema de otimização equivalente para cada problema de decisão? Caso contrário, qual é o exemplo de um problema de decisão que não possui um problema de otimização equivalente?

Luke Miles
fonte
6
Esse bit é igual a zero?
Jeffe
5
Você precisa explicar "equivalente" com mais detalhes, por exemplo, você quer dizer que um pode ser resolvido usando o outro como um oráculo / caixa preta em tempo polinomial (ou em espaço logarítmico)? Você se preocupa com todos os problemas ou apenas com problemas dentro de ? N PNP
Kaveh
11
Dependendo do seu ponto de vista, a pergunta é trivial (tome qualquer problema de decisão que não tenha um " ") ou não responda (como provar que "não existe um problema de opção equivalente"?). kk
Raphael

Respostas:

28

Como já mencionado nos comentários, isso depende das definições, como de costume. Minha tentativa de responder a isso precisa de algumas definições, portanto esse será outro exemplo de minha incapacidade de fornecer respostas concisas.


Definição: Um problema de otimização é uma tupla com(X,F,Z,)( X, F, Z, )

  • XX o conjunto de instâncias ou entradas adequadamente codificadas (cadeias) .
  • FF é uma função que mapeia cada instância para um conjunto de soluções viáveis de .xXx XF(x)F( X )xx
  • ZZ é a função objetivo que mapeia cada par , onde e , para um número real chamado valor de .(x,y)( x , y)xXx XyF(x)yF( X )Z(x,y)Z( x , y)yy
  • é a direção da otimização , ou .minminmaxmax

Definição: Uma solução ideal de uma instância de um problema de otimização é uma solução viável para a qual . O valor de uma solução ótima é indicado com O p t ( x ) e chamado de ideal .x X P Ox XPO Y F ( x ) Z ( x , y ) = { Z ( x , y ' ) | y 'F ( x ) }yF( X )Z( x , y) = { Z( x , y) | YF( x ) }O p t ( x )

Definição: O problema de avaliação , denominado P E , correspondente ao problema de otimização P O é o seguinte: Dada uma instância x X , calcule O p t ( x ) se x tiver uma solução ideal e, caso contrário, não produzir uma solução ótima.PEPOx XO p t ( x )x

Observe que isso apenas pede o valor da solução ideal, não a solução inteira com todos os seus detalhes.

Definição: O problema de decisão , denominado P D, correspondente ao problema de otimização P O, é o seguinte: Dado um par ( x , k ) , onde x X e k Q , decidem se x tem uma solução viável y tal que Z ( x , y ) k se = min e tal que Z ( x , y )PDPO( x , k )x Xk QxyZ( x , y) k= mink se= máx .Z( x , y) k= max

Uma primeira observação é agora que P SN P SP DN P . A prova não é difícil e omitida aqui.PONPOPDNP

Agora intuitivamente P E e P D correspondendo a P S não são mais difíceis do que P ó si. Para expressar formalmente esse sentimento (definindo assim o que significa equivalente ), usaremos reduções.PEPDPOPO

Lembre-se de que um idioma L 1 é redutível em tempo polinomial para outro idioma L 2 se houver uma função f , computável em tempo polinomial, tal que para todas as palavras x , x L 1f ( x ) L 2 . Esse tipo de redutibilidade é conhecido como Karp ou redutibilidade muitos-para-um , e se L 1 é redutível a L 2 dessa maneira, expressamos isso escrevendo L 1 m L 2L1L2fxxL1f(x)L2L1L2L1mL2. Este é um conceito central na definição de NP-completude.

Infelizmente, reduções muitos para um variam entre idiomas e não está claro como empregá-los no contexto de problemas de otimização. Portanto, precisamos considerar um tipo diferente de redutibilidade, a redutibilidade de Turing . Primeiro, precisamos disso:

Definição: Um oráculo para um problema P é uma sub-rotina (hipotética) que pode resolver instâncias de P em tempo constante.PP

Definição: Uma problema P 1 é de tempo polinomial Turing-redutível a um problema P 2 , escrita P 1 T P 2 , se exemplos de P 1 pode ser resolvido no tempo polinomial por um algoritmo com acesso a um Oracle para P 2 .P1P2P1TP2P1P2

Informalmente, assim como com m , a relação P 1 T P 2 expressa que P 1 não é mais difícil que P 2 . Também é fácil ver que, se P 2 pode ser resolvido em tempo polinomial, P 1 também pode . Novamente T é uma relação transitiva. O seguinte fato é óbvio:mP1TP2P1P2P2P1T

Vamos P SN P S , então P D T P E T P S .PONPOPDTPETPO

Porque, dada a solução completa, calcular seu valor e decidir se atende ao limite k são simples.k

Definição: Se por dois problemas P 1 e P 2 ambas as relações P 1 T P 2 , P 2P 1 se mantiverem, escrevemos P 1 T P 2 ; nossa noção de equivalência .P1P2P1TP2P2P1P1TP2

Estamos agora pronto para a prova de que P D T P E dado o problema de optimização correspondente é P SN P S e Z é um valor inteiro. Temos que mostrar que P E T P D se mantém. Podemos determinar { Z ( x , y ) | y F ( x ) } com um binário procurar usign o orcale para P D . A definição de NPDTPEPONPOZPETPD{Z(x,y)yF(x)}PDP ONPO assegura que | Z(x,y) | 2 q ( | x | ) para algum polinômioq, portanto, o número de etapas na pesquisa binária é polinomial em | x | . |Z(x,y)|2q(|x|)q|x|

Para um problema de otimização P O, a relação com P E é menos clara. Em muitos casos concretos, pode-se demonstrar directamente que P D T P E T P S . Para provar que isso geralmente ocorre dentro da estrutura apresentada aqui, precisamos de uma suposição adicional.POPEPDTPETPO

Primeiro, precisamos estender m de pares de idiomas para pares dos problemas de decisão correspondentes. Então é fácil ver que T é mais geral que m .mTm

Sejam P e P ' problemas de decisão; então P m P P T P . Isso ocorre porque uma redução muitos-para-um pode ser interpretada como o uso de um oráculo de maneira muito restrita: o oráculo é chamado uma vez, no final, e seu resultado também é retornado como o resultado geral. PPPmPPTP

Agora estamos prontos para o final:

Vamos P SN P O e suponha Z é número inteiro com valor e que P D é NP-completa, em seguida, P D T P E T P S . Com as observações anteriores, continua a mostrar P ó T P E . Para fazer isso, irá apresentar um problema P ' ON P S tal que P ó T P ' E . Então nós temosPONPOZPD

PDTPETPO.
POTPEPONPOPOTPEP O T P ' ET P ' DT P D T P E . O segundo e o terceiroT valem por causa da equivalência da versão de decisão e avaliação comprovada anteriormente. O terceiroT decorre da completude NP de P D e dos dois fatos mencionados anteriormente, a saber, P ON P OP DN P e P m
POTPETPDTPDTPE.
TTPDPONPOPDNPP ' OP T P ' ó .PmPOPTPO

Agora os detalhes: Assume-se que as soluções viáveis de P ó são codificados usando um alfabeto Σ equipado com uma ordem total. Seja w 0 , w 1 , as palavras de Σ listadas em ordem de comprimento não decrescente e ordem lexicográfica dentro dos blocos de palavras com comprimento comum. (Assim, w 0 é a palavra vazia.) Para todo y Σ ∗, deixe σ ( y ) denotar o inteiro único i tal que y = w i . Ambos σPOΣw0,w1,Σw0yΣσ(y)iy=wiσe σ - 1 pode ser calculado em tempo polinomial. Seja q um polinômio tal que, para todo x X e todo y F ( x ) , tenhamos σ ( y ) < 2 q ( | x | ) .σ1qxXyF(x)σ(y)<2q(|x|)

Agora o problema P ' S é idêntico ao P ó excepto para uma função objectivo modificado Z ' . Para x X e y F ( x ) , tomamos Z ( x , y ) = 2 q ( | x | )Z ( x , y ) + σ ( y ) . Z POPOZxXyF(x)Z(x,y)=2q(|x|)Z(x,y)+σ(y)Zé calculável no tempo polinomial assim P ' ON P S .PONPO

Para mostrar que P O T P ' E observamos que x é viável para P O se e somente se é viável para P ' E . Podemos assumir que esse é o caso, pois o caso oposto é trivial de lidar.POTPExPOPE

A substituição de Z por Z é monotônica no sentido de que, para todo y 1 , y 2F ( x ) , se Z ( x , y 1 ) < Z ( x , y 2 ) então Z ( x , y 1 ) < Z ( x , y 2 ) . Isso implica que toda solução ideal para xZZy1,y2F(x)Z(x,y1)<Z(x,y2)Z(x,y1)<Z(x,y2)xem P ' ó é uma solução óptima de X em P ó . Assim, a nossa tarefa reduz para o cálculo de uma solução óptima y de x em P ' ó .POxPOyxPO

Consultando o oráculo para P E , podemos obter o valor de Z ( x , y ) = 2 q ( | x | )Z ( x , y ) + σ ( y ) . Formar o restante deste número, o módulo 2 q ( | x | ) produz σ ( y ) a partir do qual y pode ser calculado em tempo polinomial.PEZ(x,y)=2q(|x|)Z(x,y)+σ(y)2q(|x|)σ(y)y

uli
fonte
"Um oráculo para um problema P é uma sub-rotina (hipotética) que pode resolver instâncias de P em tempo constante." Um oráculo deve levar apenas tempo constante?
Tim
@ Tim É claro que existem livros, listei alguns nos comentários de outra resposta
uli
@ Tim Em relação ao Oracle: Se você encontrou / concebeu uma redução A T B entre dois problemas A e B de ter reduzido o problema de encontrar um algoritmo eficiente para um a encontrar um algoritmo eficiente para B . Ou em outras palavras a redução diz-lhe que, a fim de resolver A você pode usar B . É como usar uma sub-rotina para B em um algoritmo para A . No entanto, os problemas A e BATBABABABBAAgeralmente são problemas em que não conhecemos soluções eficientes. E, no caso da redutibilidade de Turing, até a usamos nos casos em que os problemas envolvidos não são decididos.
21712 uli
Assim, B é uma sub-rotina desconhecida. Tornou-se um costume em teoria da complexidade para chamar o algoritmo hipotético para um derivado da redução como um algoritmo com a Oracle B . Chamando a sub-rotina desconhecido para B um oráculo apenas expressa que não podemos esperar para encontrar um algoritmo eficiente para B , assim como não podemos esperar obter um oráculo para B . Essa escolha é um tanto infeliz, pois conota uma habilidade mágica. O custo para o oráculo deve ser | x | como uma sub-rotina, pelo menos, leia a entrada x .
21312 uli
3
Uma excelente resposta ao redor; a única coisa que eu acrescentaria (chegando agora a ela através de outra pergunta) é que a "direção da otimização" é um pouco desnecessário de complexidade e, para concretizar, sempre podemos presumir que a função objetivo Z deve ser maximizada; se a intenção é minimizar, então podemos apenas definir uma nova função objetiva Z = - Z e reescrever toda a minimização de Z como maximização de Z .
Steven Stadnicki
5

Como dizem os comentários, a resposta depende das definições exatas. Deixe-me interpretar a questão de uma maneira muito básica (até ingênua).

Vamos S haver alguma relação, isto é S { ( a , b ) | a , b Σ * } .

Agora, definimos um problema de pesquisa para S :

Dada a , encontrar um b tal que ( a , b ) S .

e um problema de decisão para S :

Dada ( um , b ) resposta ou não ( de um , b ) S .

(for instance, in the example given in the question, S will hold all the pairs (u,v,k) such that there exists a path between u and v which is shorter than k.)

Note that these two problems are well defined. For this definition, we can ask whether the two problems are "equivalent" for any S. In "equivalent" I mean that if one of them is computable (i.e., there exists an algorithm that solves it) than the other one is computable as well. In general, they are not.

Claim 1: Decision implies Search.

Proof: Let DS be the algorithm that solves the decision problem of S. Given an input a, We can run DS(a,x) for any xΣ, one after the other, or in parallel. If there exists b such that (a,b)S, we will eventually find it. If not, the algorithm might not stop.

Claim 2: Search does not imply Decision.

The reason is that the search algorithm might return a different b than the one we need. That is, for every a there is some b that is very easy to find, but other b that is not. For instance, let L be some undecidable language, then define S={(x,0)xΣ}{(x,1)xL}.

For every x the search algorithm can return 0. But no decision algorithm can answer correctly whether (x,1)S, for all the pairs (x,1). If it could, it would have decided an undecidable problem, which is impossible.


This depends on S. If, for instance, S is bounded, there might exists an algorithm that does stop.

Ran G.
fonte
2
The right decision problem is existence of b s.t. a,bS.
Kaveh
If decision is defined as the existence of b, then search implies decision.
Ran G.
1
In a weak sense, i.e. w.r.t. computability but not complexity is a more delicate issue.
Kaveh