Оптимизация версии решения проблемы

26

Известно, что каждая проблема оптимизации / поиска имеет эквивалентную проблему решения. Например, проблема кратчайшего пути

  • версия для оптимизации / поиска: для заданного неориентированного невзвешенного графа G = ( V , E )G=(V,E) и двух вершин v , u Vv,uV найдите кратчайший путь между vv и uu .
  • версия решения: для неориентированного невзвешенного графа G = ( V , E )G=(V,E) , двух вершин v , u Vv,uV и неотрицательного целого числа kk существует ли в G путь Gмежду uu и vv , длина которого не превосходит kk ?

В общем, «Найти x XxX st f ( x ) = min { f ( x ) x X }f(x)=min{f(x)xX} !» становится "Есть ли x XxX st f ( x ) kf(x)k ?".

Но верно ли обратное, то есть существует ли эквивалентная проблема оптимизации для каждой проблемы решения? Если нет, то каков пример решения проблемы, которая не имеет эквивалентной проблемы оптимизации?

Люк Майлз
источник
6
Этот бит равен нулю?
Джефф
5
Вы должны объяснить «эквивалент» более подробно, например, имеете ли вы в виду, что одно может быть решено с использованием другого в качестве оракула / черного ящика за полиномиальное время (или в логарифмическом пространстве)? Вас волнуют все проблемы или только проблемы внутри N PNP ?
Kaveh
1
В зависимости от вашей точки зрения, вопрос является либо тривиальным (принять любую задачу решения, у которой нет « k »), либо не отвечающим (как доказать, что «нет эквивалентной опционной проблемы»?). k
Рафаэль

Ответы:

28

Как уже говорилось в комментариях, это зависит от определений, как обычно. Моя попытка ответить на это требует довольно много определений, так что это будет еще один пример моей неспособности дать краткие ответы.


Определение: задача оптимизации является кортеж ( X , F , Z , ) с(X,F,Z,)

  • X набор соответствующим образом закодированных (строковых)экземпляровиливходов.X
  • Р является функциейкоторая отображает каждый экземпляр х X к множеству F ( х ) извозможных решенийпо й .FxXF(x)x
  • Z является целевой функциейкоторая отображает каждую пару ( х , у ) , где х Х и Y F ( х ) , чтобы вещественное число Z ( х , у ) называетсязначениемпо у .Z(x,y)xXyF(x)Z(x,y)y
  • -направление оптимизации, минимальное или максимальное .minmax

Определение: оптимальное решение экземпляра х Х задачи оптимизации Р O является допустимым решением у F ( х ) , для которых Z ( х , у ) = { Z ( х , у ' ) | у 'F ( х ) } . Значение оптимального решения обозначается через O p t ( x )xXPOyF(x)Z(x,y)={Z(x,y)yF(x)}O p t ( x )и назвал оптимальным .

Определение: Задача оценки , обозначаемая P E , которая соответствует задаче оптимизации P O, является следующей: для данного случая x X вычислить O p t ( x ), если xпЕпОx XO p t ( x )Икс имеет оптимальное решение, и вывести «нет оптимального решения» в противном случае.

Обратите внимание, что это просто запрашивает значение оптимального решения, а не самого решения со всеми его деталями.

Определение. Задача решения , обозначаемая P D, которая соответствует задаче оптимизации P O, имеет следующий вид. Для пары ( x , k ) , где x X и k Q , решить, есть ли у x выполнимое решение y такое, что Z ( x , y ) k, если = min и такое, что Z ( x , y )пDпО( х , к )x XkQxyZ(x,y)k=mink, если= макс .Z(x,y)k=max

Первое наблюдение состоит в том, что в настоящее время Р ОN P OP DN P . Доказательство не сложно и здесь опущено.PONPOPDNP

Теперь интуитивно P E и P D , соответствующий P O не сложнее , чем P O сам. Чтобы выразить это чувство формально (тем самым определяя, что эквивалентноPEPDPOPO должен означать), мы будем использовать сокращения.

Напомним, что язык L 1 сводится за полиномиальное время к другому языку L 2, если существует функция f , вычислимая за полиномиальное время, такая, что для всех слов x , x L 1f ( x ) L 2 . Этот вид сводимости известен как сводимость по Карпу или многозначность , и если L 1 сводится к L 2 таким образом, мы выражаем это, записывая L 1 m L 2L1L2fxxL1f(x)L2L1L2L1mL2, Это центральное понятие в определении NP-полноты.

К сожалению, сокращения «один к одному» идут между языками, и неясно, как их использовать в контексте проблем оптимизации. Поэтому мы должны рассмотреть другой вид сводимости, сводимость по Тьюрингу . Сначала нам нужно это:

Определение: оракул для задачи P является (гипотетический) подпрограммой , которая может решить экземпляры РPP в постоянная время.

Определение: задача P 1 сводится по Тьюрингу за полиномиальное время к задаче P 2 , записанной как P 1 T P 2 , если экземпляры P 1 могут быть решены за полиномиальное время алгоритмом с доступом к оракулу для P 2 .P1P2P1TP2P1P2

Неформально, как и при m , соотношение P 1 T P 2 выражает, что P 1 не сложнее, чем P 2 . Также легко видеть, что если P 2 может быть решена за полиномиальное время, то и P 1 может быть решена . Снова T является транзитивным отношением. Следующий факт очевиден:mP1TP2P1P2P2P1T

Пусть P ON P O , то Р Д Т Р Е T P O .PONPOPDTPETPO

Потому что , учитывая полное решение, вычисляя его значение и решить , отвечает ли она связанного Kk , просто.

Определение: если для двух задач P 1 и P 2 выполняются оба отношения P 1 T P 2 , P 2P 1 , пишем P 1 T P 2 ; наше понятие эквивалентности .P1P2P1TP2P2P1P1TP2

Теперь мы готовы доказать, что P D T P E, если соответствующая задача оптимизации имеет вид P ON P O, а Z целочисленное. Мы должны показать, что P E T P D имеет место. Мы можем определить { Z ( х , Y ) | у F ( х ) } с бинарным поиском usign в Orcale для P D . Определение NPDTPEPONPOZPETPD{Z(x,y)yF(x)}PD Р ONPO гарантирует, что | Z(х,у) | 2 q ( | x | ) для некоторого полиномаq, поэтому число шагов в бинарном поиске является полиномиальным от | х | , |Z(x,y)|2q(|x|)q|x|

Для задачи оптимизации P O отношение к P E менее ясно. Во многих конкретных случаях можно прямо показать, что P D T P E T P OPOPEPDTPETPO. To prove that this holds generally within the framework given here we need an additional assumption.

First we need to extend mm from pairs of languages to pairs of the corresponding decision problems. Then it is easy to see that TT is more general than mm.

Let PP and PP be decision problems; then PmPPTPPmPPTP. This holds because a many-to-one reduction can be interpreted as making use of an oracle in a very restricted way: The oracle is called once, at the very end, and its result is also returned as the overall result.

Now we are ready for the finale:

Let PONPOPONPO and suppose ZZ is integer-valued and that PDPD is NP-complete, then PDTPETPO.

PDTPETPO.
With the previous observations it remains to show POTPEPOTPE. To do this we will exhibit a problem PONPOPONPO such that POTPEPOTPE. Then we have POTPETPDTPDTPE.
POTPETPDTPDTPE.
The second and third TT hold because of the equivalence of the decision and evaluation version proofed earlier. The third TT follows from the NP-completness of PDPD and the two facts mentioned before, namely PONPOPDNPPONPOPDNP and PmPOPTPOPmPOPTPO.

Now the details: Assume that the feasible solutions of POPO are encoded using an alphabet ΣΣ equipped with a total order. Let w0,w1,w0,w1, be the words from ΣΣ listed in order of nondecreasing length and lexicographic order within the blocks of words with common length. (Thus w0w0 is the empty word.) For all yΣyΣ let σ(y)σ(y) denote the unique integer ii such that y=wiy=wi. Both σσ and σ1σ1 can be computed in polynomial time. Let qq be a polynomial such that for all xXxX and all yF(x)yF(x) we have σ(y)<2q(|x|)σ(y)<2q(|x|).

Now the problem POPO is identical to POPO except for a modified objective function ZZ. For xXxX and yF(x)yF(x) we take Z(x,y)=2q(|x|)Z(x,y)+σ(y)Z(x,y)=2q(|x|)Z(x,y)+σ(y). ZZ is computable in polynomial time thus PONPOPONPO.

To show that POTPEPOTPE we observe that xx is feasible for POPO if and only if it is feasible for PEPE. We can assume that this is the case, since the opposite case is trivial to handle.

The substituion of ZZ for ZZ is monotonic in the sense that for all y1,y2F(x)y1,y2F(x), if Z(x,y1)<Z(x,y2)Z(x,y1)<Z(x,y2) then Z(x,y1)<Z(x,y2)Z(x,y1)<Z(x,y2). This implies that every optimal solution for xx in POPO is an optimal solution of xx in POPO. Thus our task reduces to the computation of an optimal solution yy of xx in POPO.

Querying the oracle for PEPE we can get the value of Z(x,y)=2q(|x|)Z(x,y)+σ(y)Z(x,y)=2q(|x|)Z(x,y)+σ(y). Forming the remainder of this number modulo 2q(|x|)2q(|x|) yields σ(y) from which y can be computed in polynomial time.

uli
источник
"An oracle for a problem P is a (hypothetical) subroutine that can solve instances of P in constant time." Must an oracle take only constant time?
Tim
@Tim Of course there are books, I listed a few in the comments of another answer
uli
@Tim Regarding the oracle: If you have found/conceived a reduction ATB between two problems A and B you have reduced the problem of finding an efficient algorithm for A to finding an efficient algorithm for B. Or in other words the reduction tells you that in order to solve A you can use B. It is like using a subroutine for B in an algorithm for A. However the problems A and B are often problems where we don’t know efficient solutions. And in case of Turing-reducibility we even use it in cases where the problems involved aren’t decidable at all.
uli
@Tim Thus B is an unknown subroutine. It has become a custom in complexity theory to call the hypothetical algorithm for A derived from the reduction as an algorithm with oracle B. Calling the unknown subroutine for B an oracle just expresses that we can’t hope to find an efficient algorithm for B just as we can’t hope to obtain an oracle for B. This choice is somewhat unfortunate, as it connotes a magical ability. The cost for the oracle should be |x| as a subroutine has at least to read the input x.
uli
3
An excellent answer all around; the only thing I would add (coming at it now via another question) is that the 'optimization direction' is a needless bit of complexity and for concreteness we can always presume that the objective function Z is to be maximized; if the intention is to minimize, then we can just define a new objective function Z=Z and rewrite all the minimization of Z as maximization of Z.
Steven Stadnicki
5

As the comments say, the answer depends on the exact definitions. Let me interpret the question in a very basic (even naïve) way.

Let S be some relation, that is S{(a,b)a,bΣ}.

Now we define a search problem for S:

Given a, find a b such that (a,b)S.

and a decision problem for S:

Given (a,b) answer whether or not (a,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.
источник
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