Einfach zu optimieren, aber schwer zu bewerten

10

Gibt es bekannte natürliche Beispiele für Optimierungsprobleme, für die es viel einfacher ist, eine optimale Lösung zu erstellen, als die Qualität einer bestimmten Kandidatenlösung zu bewerten?

Der Vollständigkeit halber können wir polynomzeitlösbare Optimierungsprobleme der Form betrachten: "gegebenes x, minimiere ", wobei f : { 0 , 1 } × { 0 , 1 } N. ist zum Beispiel # P-schwer. Solche Probleme existieren eindeutig (zum Beispiel könnten wir f ( x , 0 ) = 0 für alle x haben, selbst wenn f nicht berechenbar ist), aber ich suche nach "natürlichen" Problemen, die dieses Phänomen aufweisen.f(x,y)f:{0,1}×{0,1}Nf(x,0)=0xf

David
quelle

Antworten:

3

In Artikel [1] gibt es ein Problem mit der Eigenschaft, dass das Finden eines optimalen Elements Polynomzeit benötigt, obwohl die Berechnung der Zielfunktionswerte NP-schwer ist (dies bedeutet, dass die Bewertung der Qualität einer bestimmten Kandidatenlösung auch NP-schwer ist ).

[1] TCECheng, Y. Shafransky, CTNg. Ein alternativer Ansatz zum Nachweis der NP-Härte von Optimierungsproblemen. European Journal of Operational Research 248 (2016) 52–58.

Yakov Shafransky

Yakov Shafransky
quelle
Es wäre schön, hier mehr Details zu teilen. :)
Michael Wehar
15

Hier ist ein Beispiel, in dem man eine Lösung in Polynomzeit herstellen kann, die Bewertung einer gegebenen Lösung jedoch NP- hart ist.

n,kkn

nk

T(n,k)k

Hinweis: Wenn wir nur überprüfen möchten, ob die Lösung optimal ist , ist dies einfach, da das Turan-Diagramm als eindeutiges Optimum bekannt ist. Es reicht also aus, das Kandidatendiagramm mit dem Turan-Diagramm zu vergleichen, das eine einfache Struktur aufweist . Wenn wir andererseits die Qualität einer Kandidatenlösung bewerten möchten , wie in der Frage gefordert, dh ob sie machbar ist und wie weit sie vom Optimum entfernt ist, müssen wir prüfen, ob sie die maximale Clique erfüllt Zwang.

Andras Farago
quelle