Известно, что каждая проблема оптимизации / поиска имеет эквивалентную проблему решения. Например, проблема кратчайшего пути
- версия для оптимизации / поиска: для заданного неориентированного невзвешенного графа G = ( V , E )
G=(V,E) и двух вершин v , u ∈ Vv,u∈V найдите кратчайший путь между vv и uu .- версия решения: для неориентированного невзвешенного графа G = ( V , E )
G=(V,E) , двух вершин v , u ∈ Vv,u∈V и неотрицательного целого числа kk существует ли в G путьG между uu и vv , длина которого не превосходит kk ?
В общем, «Найти x ∗ ∈ X
Но верно ли обратное, то есть существует ли эквивалентная проблема оптимизации для каждой проблемы решения? Если нет, то каков пример решения проблемы, которая не имеет эквивалентной проблемы оптимизации?
Ответы:
Как уже говорилось в комментариях, это зависит от определений, как обычно. Моя попытка ответить на это требует довольно много определений, так что это будет еще один пример моей неспособности дать краткие ответы.
Определение: задача оптимизации является кортеж ( X , F , Z , ⊙ ) с(X,F,Z,⊙)
Определение: оптимальное решение экземпляра х ∈ Х задачи оптимизации Р O является допустимым решением у ∈ F ( х ) , для которых Z ( х , у ) = ⊙ { Z ( х , у ' ) | у ' ∈ F ( х ) } . Значение оптимального решения обозначается через O p t ( x )x∈X PO y∈F(x) Z(x,y)=⊙{Z(x,y′)∣y′∈F(x)} O p t ( x ) и назвал оптимальным .
Определение: Задача оценки , обозначаемая P E , которая соответствует задаче оптимизации P O, является следующей: для данного случая x ∈ X вычислить O p t ( x ), если xпЕ пО x ∈ X O 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 ∈ X k∈Q x y Z(x,y)≤k ⊙=min ≥ k, если ⊙ = макс .Z(x,y)≥k ⊙=max
Первое наблюдение состоит в том, что в настоящее время Р О ∈ N P O ⇒ P D ∈ N P . Доказательство не сложно и здесь опущено.PO∈NPO⇒PD∈NP
Теперь интуитивно P E и P D , соответствующий P O не сложнее , чем P O сам. Чтобы выразить это чувство формально (тем самым определяя, что эквивалентноPE PD PO PO должен означать), мы будем использовать сокращения.
Напомним, что язык L 1 сводится за полиномиальное время к другому языку L 2, если существует функция f , вычислимая за полиномиальное время, такая, что для всех слов x , x ∈ L 1 ⇔ f ( x ) ∈ L 2 . Этот вид сводимости известен как сводимость по Карпу или многозначность , и если L 1 сводится к L 2 таким образом, мы выражаем это, записывая L 1 ≤ m L 2L1 L2 f x x∈L1⇔f(x)∈L2 L1 L2 L1≤mL2 , Это центральное понятие в определении NP-полноты.
К сожалению, сокращения «один к одному» идут между языками, и неясно, как их использовать в контексте проблем оптимизации. Поэтому мы должны рассмотреть другой вид сводимости, сводимость по Тьюрингу . Сначала нам нужно это:
Определение: оракул для задачи P является (гипотетический) подпрограммой , которая может решить экземпляры РP P в постоянная время.
Определение: задача P 1 сводится по Тьюрингу за полиномиальное время к задаче P 2 , записанной как P 1 ≤ T P 2 , если экземпляры P 1 могут быть решены за полиномиальное время алгоритмом с доступом к оракулу для P 2 .P1 P2 P1≤TP2 P1 P2
Неформально, как и при ≤ m , соотношение P 1 ≤ T P 2 выражает, что P 1 не сложнее, чем P 2 . Также легко видеть, что если P 2 может быть решена за полиномиальное время, то и P 1 может быть решена . Снова ≤ T является транзитивным отношением. Следующий факт очевиден:≤m P1≤TP2 P1 P2 P2 P1 ≤T
Пусть P O ∈ N P O , то Р Д ≤ Т Р Е ≤ T P O .PO∈NPO PD≤TPE≤TPO
Потому что , учитывая полное решение, вычисляя его значение и решить , отвечает ли она связанного Kk , просто.
Определение: если для двух задач P 1 и P 2 выполняются оба отношения P 1 ≤ T P 2 , P 2 ≤ P 1 , пишем P 1 ≡ T P 2 ; наше понятие эквивалентности .P1 P2 P1≤TP2 P2≤P1 P1≡TP2
Теперь мы готовы доказать, что P D ≡ T P E, если соответствующая задача оптимизации имеет вид P O ∈ N P O, а Z целочисленное. Мы должны показать, что P E ≤ T P D имеет место. Мы можем определить ⊙ { Z ( х , Y ) | у ∈ F ( х ) } с бинарным поиском usign в Orcale для P D . Определение NPD≡TPE PO∈NPO Z PE≤TPD ⊙{Z(x,y)∣y∈F(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 OPO PE PD≡TPE≡TPO . To prove that this holds generally within the framework given here we need an additional assumption.
First we need to extend ≤m≤m from pairs of languages to pairs of the corresponding decision problems. Then it is easy to see that ≤T≤T is more general than ≤m≤m .
Let PP and P′P′ be decision problems; then P≤mP′⇒P≤TP′P≤mP′⇒P≤TP′ . 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 PO∈NPOPO∈NPO and suppose ZZ is integer-valued and that PDPD is NP-complete, then PD≡TPE≡TPO.
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 x∈Xx∈X and all y∈F(x)y∈F(x) we have σ(y)<2q(|x|)σ(y)<2q(|x|) .
Now the problem P′OP′O is identical to POPO except for a modified objective function Z′Z′ . For x∈Xx∈X and y∈F(x)y∈F(x) we take Z′(x,y)=2q(|x|)⋅Z(x,y)+σ(y)Z′(x,y)=2q(|x|)⋅Z(x,y)+σ(y) . Z′Z′ is computable in polynomial time thus P′O∈NPOP′O∈NPO .
To show that PO≤TP′EPO≤TP′E we observe that xx is feasible for POPO if and only if it is feasible for P′EP′E . We can assume that this is the case, since the opposite case is trivial to handle.
The substituion of Z′Z′ for ZZ is monotonic in the sense that for all y1,y2∈F(x)y1,y2∈F(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 P′OP′O is an optimal solution of xx in POPO . Thus our task reduces to the computation of an optimal solution yy of xx in P′OP′O .
Querying the oracle for P′EP′E 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.
источник
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:
and a decision problem for 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)∣x∈L}.
† This depends on S. If, for instance, S is bounded, there might exists an algorithm that does stop.
источник