Versi optimisasi masalah keputusan

26

Diketahui bahwa setiap masalah optimasi / pencarian memiliki masalah keputusan yang setara. Misalnya masalah jalur terpendek

  • versi optimisasi / pencarian: Diberikan grafik tidak tertimbang yang tidak diarahkan G = ( V , E )G=(V,E) dan dua simpul v , u Vv,uV , temukan jalur terpendek antara vv dan uu .
  • versi keputusan: Diberikan grafik tak tertimbang tidak berarah G = ( V , E )G=(V,E) , dua simpul v , u Vv,uV , dan bilangan bulat non-negatif kk , adakah jalur di GG antara uu dan vv yang panjangnya paling banyak kk ?

Secara umum, "Temukan x XxX st f ( x ) = min { f ( x ) x X }f(x)=min{f(x)xX} !" menjadi "Apakah ada x XxX st f ( x ) kf(x)k ?".

Tetapi apakah kebalikannya juga benar, yaitu apakah ada masalah optimasi yang setara untuk setiap masalah keputusan? Jika tidak, apa contoh masalah keputusan yang tidak memiliki masalah optimasi yang setara?

Luke Miles
sumber
6
Apakah bit ini sama dengan nol?
JeffE
5
Anda harus menjelaskan "ekuivalen" lebih terinci, misalnya apakah maksud Anda satu dapat diselesaikan menggunakan yang lain sebagai oracle / blackbox dalam waktu polinomial (atau dalam ruang logaritmik)? Apakah Anda peduli dengan semua masalah atau hanya masalah di dalam N PNP ?
Kaveh
1
Bergantung pada sudut pandang Anda, pertanyaannya adalah sepele (mengambil masalah keputusan apa pun yang tidak memiliki " kk ") atau tidak dapat dijawab (bagaimana membuktikan bahwa "tidak ada masalah pilihan yang setara"?).
Raphael

Jawaban:

28

Seperti yang sudah dinyatakan dalam komentar, itu tergantung pada definisi, seperti biasa. Upaya saya untuk menjawab ini membutuhkan beberapa definisi, jadi ini akan menjadi contoh lain dari ketidakmampuan saya untuk memberikan jawaban yang ringkas.


Definisi: Sebuah masalah optimasi adalah tuple ( X , F , Z , ) dengan(X,F,Z,)

  • X setinstance(input) yang dikodekan (string)atauinput.X
  • F adalah fungsi yang memetakan setiap contoh x X untuk satu set F ( x ) darisolusi layakdari x .FxXF(x)x
  • Z adalah fungsi tujuan yang memetakan setiap pasangan ( x , y ) , dimana x X dan y F ( x ) , untuk bilangan real Z ( x , y ) disebutnilaidari y .Z(x,y)xXyF(x)Z(x,y)y
  • adalaharah optimasi, baik min atau maks .minmax

Definisi: Sebuah solusi yang optimal dari sebuah contoh x X dari masalah optimasi P O adalah solusi yang layak y F ( x ) yang Z ( x , y ) = { Z ( x , y ' ) | y 'F ( x ) } . Nilai solusi optimal dilambangkan dengan O p t ( x )xXPOyF(x)Z(x,y)={Z(x,y)yF(x)}Opt(x)dan disebut optimal .

Definisi: The masalah evaluasi , dilambangkan P E , sesuai dengan masalah optimasi P O adalah sebagai berikut: Mengingat contoh x X , menghitung O p t ( x ) jika x memiliki solusi yang optimal dan output “tidak ada solusi optimal” sebaliknya.PEPOxXOpt(x)x

Perhatikan bahwa ini hanya meminta nilai solusi optimal bukan seluruh solusi itu sendiri dengan semua perinciannya.

Definisi: Masalah keputusan , dilambangkan P D terkait dengan masalah optimisasi P O adalah sebagai berikut: Diberikan pasangan ( x , k ) , di mana x X dan k Q , putuskan apakah x memiliki solusi yang layak y sedemikian rupa sehingga Z ( x , y ) k jika = min dan sedemikian rupa sehingga Z ( x , y )PDPO(x,k)xXkQxyZ(x,y)k=minkZ(x,y)k if =max=max.

A first observation is now that PONPOPDNPPONPOPDNP. The proof is not difficult and omitted here.

Now intuitively PEPE and PDPD corresponding to POPO are not more difficult than POPO itself. To express this feeling formally (thereby defining what equivalent is supposed to mean) we will use reductions.

Recall that a language L1L1 is polynomial-time reducible to another language L2L2 if there is a function ff, computable in polynomial time, such that for all words xx, xL1f(x)L2xL1f(x)L2. This kind of reducibility is known as Karp or many-to-one reducibility, and if L1L1 is reducible to L2L2 in this manner, we express this by writing L1mL2L1mL2. This is a central concept in the definition of NP-completness.

Unfortunately, many-to-one reductions go between languages and it is not clear how to employ them in the context of optimization problems. Therefore we need to consider a different kind of reducibility, Turing reducibility. First we need this:

Definition: An oracle for a problem PP is a (hypothetical) subroutine that can solve instances of PP in constant time.

Definition: A problem P1P1 is polynomial-time Turing-reducible to a problem P2P2, written P1TP2P1TP2, if instances of P1P1 can be solved in polynomial time by an algorithm with access to an oracle for P2P2.

Informally, just as with mm, the relation P1TP2P1TP2 expresses, that P1P1 is no more difficult than P2P2. It is also easy to see that if P2P2 can be solved in polynomial time, so can P1P1. Again TT is a transitive relation. The following fact is obvious:

Let PONPOPONPO, then PDTPETPOPDTPETPO.

Because given the full solution, computing its value and deciding whether it meets the bound kk is simple.

Definition: If for two problems P1P1 and P2P2 both relations P1TP2P1TP2, P2P1P2P1 hold, we write P1TP2P1TP2; our notion of equivalence.

We are now ready to proof that PDTPEPDTPE given the corresponding optimization problem is PONPOPONPO and ZZ is integer valued. We have to show that PETPDPETPD holds. We can determine {Z(x,y)yF(x)}{Z(x,y)yF(x)} with a binary search usign the orcale for PDPD. The definition of NPONPO ensures that |Z(x,y)|2q(|x|)|Z(x,y)|2q(|x|) for some polynomial qq, so the number of steps in the binary search is polynomial in |x||x|.

For an optimization problem POPO the relation to PEPE is less clear. In many concrete cases, one can show directly that PDTPETPOPDTPETPO. 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 q be a polynomial such that for all xX and all yF(x) we have σ(y)<2q(|x|).

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

To show that POTPE we observe that x is feasible for PO if and only if it is feasible for PE. We can assume that this is the case, since the opposite case is trivial to handle.

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

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

uli
sumber
"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.
sumber
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