Mudah dioptimalkan tetapi sulit untuk dievaluasi

Adakah contoh alami masalah optimasi yang diketahui yang lebih mudah menghasilkan solusi optimal daripada mengevaluasi kualitas solusi kandidat yang diberikan?

Demi konkret, kami dapat mempertimbangkan masalah optimisasi waktu-terpecahkan polinomial dari bentuk: "diberikan x, minimalkan ", di mana adalah, katakanlah, # P-hard. Masalah seperti itu jelas ada (misalnya, kita bisa memiliki untuk semua bahkan jika tidak dapat dihitung), tetapi saya mencari masalah `` alami '' yang menunjukkan fenomena ini.$f(x, y)$$f:\{0,1\}^*\times\{0,1\}^* \to \mathbb{N}$$f(x, 0) = 0$$x$$f$

Dalam makalah [1], ada masalah dengan properti yang menemukan elemen optimal membutuhkan waktu polinomial meskipun menghitung nilai fungsi objektif NP-keras (itu berarti bahwa mengevaluasi kualitas solusi kandidat yang diberikan adalah NP-keras juga ).

[1] TCECheng, Y.Shafransky, CTNg. Pendekatan alternatif untuk membuktikan NP-hardness masalah optimisasi. European Journal of Operational Research 248 (2016) 52–58.

Yakov Shafransky

Berikut adalah contoh, di mana seseorang dapat menghasilkan solusi dalam waktu polinomial, tetapi mengevaluasi solusi yang diberikan adalah NP -hard.

Input: Bilangan bulat positif (dalam pengkodean unary), dengan .$n,k$$k\leq n$

Tugas: Maksimalkan jumlah tepi dalam grafik -vertex di bawah batasan bahwa ukuran klik maksimumnya paling banyak .$n$$k$

Solusi: Dari teori grafik ekstrem diketahui bahwa grafik optimal adalah grafik Turan (lihat di sini ), yang dapat dengan mudah dikonstruksikan dalam waktu polinomial. Di sisi lain, memeriksa kualitas solusi kandidat yang diberikan (grafik yang diberikan) melibatkan memeriksa bahwa ukuran klik maksimumnya paling banyak , yaitu NP-keras .$T(n,k)$$k$

Catatan: Jika kita hanya ingin memeriksa apakah solusinya optimal , maka itu mudah, karena grafik Turan dikenal sebagai optimal unik, sehingga cukup untuk membandingkan kandidat kandidat dengan grafik Turan, yang memiliki struktur sederhana . Di sisi lain, jika kita ingin mengevaluasi kualitas solusi kandidat, seperti yang diminta dalam pertanyaan, yaitu, apakah layak dan seberapa jauh dari optimal, maka kita harus memeriksa apakah itu memenuhi klik maksimum paksaan.