Łatwy w optymalizacji, ale trudny do oceny

Czy są znane naturalne przykłady problemów z optymalizacją, dla których znacznie łatwiej jest stworzyć optymalne rozwiązanie niż ocenić jakość danego rozwiązania kandydującego?

Ze względu na konkretność możemy rozważyć rozwiązania problemów optymalizacji w postaci wielomianowej w postaci: „biorąc x, zminimalizuj ”, gdzie f : { 0 , 1 } ∗ × { 0 , 1 } ∗ → N jest, powiedzmy, # P-trudny. Takie problemy oczywiście istnieją (na przykład moglibyśmy mieć f ( x , 0 ) = 0 dla wszystkich x, nawet jeśli f jest nieobliczalny), ale szukam `` naturalnych '' problemów wykazujących to zjawisko.$f(x, y)$$f:\{0,1\}^*\times\{0,1\}^* \to \mathbb{N}$$f(x, 0) = 0$$x$$f$

W pracy [1] występuje problem z właściwością polegającą na tym, że znalezienie optymalnego elementu zajmuje czas wielomianowy, mimo że obliczenie wartości funkcji celu jest trudne dla NP (oznacza to, że ocena jakości danego rozwiązania kandydującego jest również trudna dla NP ).

[1] TCECheng, Y.Shafransky, CTNg. Alternatywne podejście do udowodnienia twardości NP problemów optymalizacyjnych. European Journal of Operational Research 248 (2016) 52–58.

Jakow Shafransky

Oto przykład, w którym można uzyskać rozwiązanie w czasie wielomianowym, ale ocena danego rozwiązania jest NP- twarda.

$n,k$$k\leq n$

$n$$k$

$T(n,k)$$k$

Uwaga: Jeśli chcemy tylko sprawdzić, czy rozwiązanie jest optymalne , to jest to łatwe, ponieważ wiadomo, że wykres Turana jest unikalnym optymalnym, więc wystarczy porównać wykres kandydujący z wykresem Turana, który ma prostą strukturę . Z drugiej strony, jeśli chcemy ocenić jakość rozwiązania kandydującego, zgodnie z żądaniem zawartym w pytaniu, to znaczy, czy jest to wykonalne i jak daleko jest od optymalnego, musimy sprawdzić, czy spełnia on maksymalną klikę przymus.