Masalah optimisasi dengan karakterisasi yang baik, tetapi tidak ada algoritma waktu polinomial

Pertimbangkan masalah pengoptimalan dari formulir berikut. Misalkan $f(x)$ menjadi fungsi yang dapat dihitung polinomial-waktu yang memetakan string menjadi bilangan rasional. Masalah optimasinya adalah ini: berapakah nilai maksimum atas bit string ?f ( x ) $x$$f(x)$$n$$x$

Mari kita katakan bahwa masalah seperti itu memiliki karakterisasi minimax , jika ada fungsi computable polinomial-waktu lain , sehingga berlaku. Di sini x berjalan di atas semua string n- bit, dan y berjalan di atas semua string m- bit; n dan m mungkin berbeda, tetapi mereka terkait secara polinomi.$g$xnymn

Banyak masalah optimasi alami dan penting memiliki karakterisasi minimal seperti itu. Beberapa contoh (teorema yang menjadi dasar penokohannya ditunjukkan dalam tanda kurung):

Pemrograman Linier (LP Dualitas Thm), Aliran Maksimum (Max Flow Min Cut Thm), Pencocokan Bipartit Max (Konig-Hall Thm), Pencocokan Non-Bipartit Max (Tht Thm, rumus Tutte-Berge), Max Disjoint Arborescences dalam grafik berarah ( Edmond's Disjoint Branching Thm), Max Spanning Tree Packing dalam grafik tidak berarah (Tutte's Tree Packing Thm), Min Menutupi oleh Hutan (Nash-Williams Thm), Max Packing Sutradara Cut (Lucchesi-Younger Thm), Max 2-Matroid Intersection (Intersection Matroid) Thm), Max Disjoint Paths (Menger's Thm), Max Antichain dalam Set Pesanan Sebagian (Dilworth Thm), dan banyak lainnya.

Dalam semua contoh ini, algoritma waktu polinomial juga tersedia untuk menemukan yang optimal. Pertanyaan saya:

Apakah ada masalah optimisasi dengan karakterisasi minimax, yang sejauh ini belum ditemukan algoritma polinomial-waktu?

Catatan: Pemrograman Linier berada dalam status ini selama sekitar 30 tahun!

Dalam beberapa hal teknis Anda bertanya apakah . Misalkan , dengan demikian ada poli-waktu dan sehingga iff dan iff . Ini dapat kembali sebagai karakterisasi oleh jika dan sebaliknya; jika dan sebaliknya. Sekarang memang kita memiliki .L ∈ N P ∩ c o N P F G x ∈ L ∃ y : F ( x , y ) x ∉ L ∃ y : G ( x , y ) f x ( y ) = 1 F ( x , y ) f x ( $P = NP \cap coNP$$L \in NP \cap coNP$$F$$G$$x \in L$$\exists y: F(x,y)$$x \not\in L$$\exists y: G(x,y)$$f_x(y) = 1$$F(x,y)$g x ( y ) = 0 G ( x , y ) g x ( y ) = 1 m a x y f x ( y ) = m i n y g x ( y $f_x(y) = 0$$g_x(y) = 0$$G(x,y)$$g_x(y) = 1$$max_y f_x(y) = min_y g_x(y)$

Jadi dalam hal ini, setiap masalah yang diketahui berada dalam tetapi tidak diketahui berada di dapat diubah menjadi jawaban untuk pertanyaan Anda. Misalnya Anjak (katakanlah, versi keputusan apakah bit ke - dari faktor terbesar adalah 1).P $NP \cap coNP$$P$$i$

Seymour dan Thomas menunjukkan karakterisasi min-max treewidth. Namun, lebar pohon adalah NP-hard. Namun ini bukan jenis karakterisasi yang Anda minta, karena fungsi ganda bukan fungsi yang dapat dihitung waktu polinomial dari sertifikat pendek. Ini kemungkinan besar tidak dapat dihindari untuk masalah lengkap NP, karena kalau tidak kita akan memiliki masalah NP-lengkap dalam coNP, menyiratkan runtuhnya NP = coNP, dan saya akan menganggap itu cukup mengejutkan.$g$

The treewidth dari grafik adalah sama dengan lebar terkecil terkecil dari dekomposisi pohon G . Dekomposisi pohon pada grafik G adalah pohon T sehingga setiap simpul x dari T diberi label oleh himpunan S ( x ) dari simpul G dengan properti:$G$$G$$G$$T$$x$$T$$S(x)$$G$

1. Untuk semua , | S ( x ) | ≤ k + 1 .$x \in V(T)$$|S(x)| \leq k+1$
2. Gabungan dari semua adalah titik set G .$S(x)$$G$
3. Untuk setiap , subgraf T yang diinduksi oleh semua x yang terhubung dengan u ∈ S ( x ) .$u \in V(G)$$T$$x$$u \in S(x)$
4. Setiap tepi adalah himpunan bagian dari beberapa S ( x ) untuk x ∈ V ( T ) .$(u, v) \in E(G)$$S(x)$$x \in V(T)$

Seymour dan Thomas menunjukkan bahwa treewidth sama dengan jumlah semak duri dari : maksimum k sehingga ada koleksi subgraphs terhubung dari G sehingga:$G$$k$$G$

1. Masing-masing dua subgraph berpotongan atau dihubungkan oleh suatu tepi.
2. Tidak ada set simpul G yang menyentuh semua subgraf.$k$$G$

Kumpulan subgraph seperti itu disebut duri ordo $k$

Perhatikan bagaimana "angka bramble setidaknya " adalah pernyataan ∃ ∀ , dengan kedua bilangan kuantitatif di atas set besar secara eksponensial. Jadi tidak menyarankan sertifikat yang mudah diverifikasi (dan jika ada yang akan menjadi berita besar, seperti yang saya katakan di atas). Untuk membuat hal-hal lebih buruk lagi, Grohe dan Marx menunjukkan bahwa untuk setiap k ada grafik treewidth k sehingga setiap semak duri pesanan setidaknya k 1 / 2 + ε harus terdiri dari eksponensial banyak subgraphs. Mereka juga menunjukkan bahwa terdapat semak order k 1 / 2 / O ( log $k$$\exists\forall$$k$$k$$k^{1/2 + \epsilon}$ dari ukuran polinomial.$k^{1/2}/O(\log^2 k)$

Game paritas, game Mean-payoff, game dengan diskon, dan game Stochastic Sederhana termasuk dalam kategori ini.

Semuanya adalah permainan zero-sum dua pemain tanpa batas yang dimainkan pada grafik, di mana pemain mengontrol simpul dan memilih tempat token selanjutnya. Semua memiliki kesetimbangan dalam strategi posisi tanpa memori, yang berarti bahwa setiap pemain memilih keunggulan pada setiap titik pilihan secara deterministik dan terlepas dari sejarah permainan. Dengan strategi satu pemain, respons terbaik pemain lain dapat dihitung dalam waktu polinomial, dan hubungan min-max yang Anda perlukan berlaku untuk "nilai" permainan.

Varian keputusan alami dari masalah ini adalah NP dan co-NP (memang UP dan co-UP) dan masalah fungsi, untuk menemukan keseimbangan, terletak pada PLS dan PPAD.

Algoritma dengan waktu berjalan paling dikenal adalah sub-eksponensial, tetapi super polinomial (misalnya , di mananadalah jumlah simpul dalam grafik game).$O(n^\sqrt{n})$$n$

Lihat, misalnya,

David S. Johnson. 2007. Kolom NP-kelengkapan: Menemukan jarum di tumpukan jerami. ACM Trans. Algoritma 3, 2, Pasal 24 (Mei 2007). DOI = 10.1145 / 1240233.1240247 http://doi.acm.org/10.1145/1240233.1240247