Kompleksitas parameter dari P ke NP-hard dan kembali lagi

Saya mencari contoh masalah dengan parametrized oleh angka $k \in \mathbb{N}$ , di mana kekerasan masalahnya non-monotonik dalam $k$ . Sebagian besar masalah (dalam pengalaman saya) memiliki transisi fase tunggal, misalnya $k$ -SAT memiliki transisi fase tunggal dari $k \in \{1,2\}$ (di mana masalahnya ada di P) ke $k \ge 3$ (di mana masalahnya adalah NP- lengkap). Saya tertarik pada masalah di mana ada transisi fase di kedua arah (dari mudah ke keras dan sebaliknya) karena $k$ meningkat.

Pertanyaan saya agak mirip dengan yang diajukan di Hardness Jumps in Computational Complexity , dan pada kenyataannya beberapa tanggapan di sana relevan dengan pertanyaan saya.

Contoh yang saya ketahui:

1. $k$ -colorability dari grafik planar: Dalam P kecuali ketika$k=3$ , yang merupakan NP-complete.
2. Steiner tree dengan terminal $k$ : Dalam P ketika $k=2$ (runtuh ke jalur $s$ - terpendek $t$) dan ketika $k=n$ (runtuh ke MST), tetapi NP-hard "di antara". Saya tidak tahu apakah transisi fase ini tajam (misalnya, P untuk $k_0$ tapi NP-keras untuk $k_0+1$ ). Transisi $k$ bergantung pada ukuran instance input, tidak seperti contoh saya yang lain.
3. Menghitung tugas memuaskan dari rumus planar modulo $n$ : Dalam P ketika $n$ adalah Mersenne prima sejumlah $n=2^k-1$ , dan # P-lengkap untuk (?) Yang paling / semua nilai-nilai lain dari $n$ (dari Aaron Sterling di thread ini ) . Banyak transisi fase!
4. Deteksi subgraph yang diinduksi: Masalahnya tidak ditentukan oleh integer tetapi grafik. Ada grafik $H_1 \subseteq H_2 \subseteq H_3$ (di mana $\subseteq$ menunjukkan jenis hubungan subgraph tertentu), yang menentukan apakah $H_i \subseteq G$ untuk grafik yang diberikan $G$ adalah dalam P untuk $i\in \{1,3\}$ tetapi NP- lengkap untuk $i=2$ . (dari Hsien-Chih Chang di utas yang sama ).

Satu bidang dengan banyak kompleksitas masalah non-monoton adalah pengujian properti. Biarkan menjadi himpunan semua grafik n -vertex, dan panggil P ⊆ G n properti grafik. Masalah umum adalah untuk menentukan apakah grafik G memiliki properti P (yaitu G ∈ P ) atau 'jauh' dari memiliki properti P dalam arti tertentu. Bergantung pada P apa itu, dan apa jenis akses kueri yang Anda miliki pada grafik, masalahnya bisa sangat sulit.$\mathcal{G}_n$$n$$P \subseteq \mathcal{G}_n$$G$$P$$G \in P$$P$$P$

Tetapi mudah untuk melihat bahwa masalah non-monoton, dalam bahwa jika kita memiliki , fakta bahwa P adalah mudah diuji tidak berarti baik bahwa S adalah mudah diuji atau yang T adalah. $S \subset P \subset T$$P$$S$$T$

Untuk melihat ini, cukup untuk mengamati bahwa dan P = ∅ keduanya dapat diuji secara trivial, tetapi untuk beberapa properti, terdapat batas bawah yang kuat.$P = \mathcal{G}_n$$P = \emptyset$

Untuk grafik dan bilangan bulat k ≥ 1 , kekuatan k -th G , dilambangkan oleh G k , memiliki himpunan simpul yang sama sehingga dua simpul berbeda berdekatan dalam G k jika jarak mereka dalam G paling banyak k . Kekuatan k -th dari masalah graph split menanyakan apakah grafik yang diberikan adalah kekuatan k -th dari grafik split.$G$$k\ge 1$$k$$G$$G^k$$G^k$$G$$k$$k$$k$

• Untuk , masalah terpecahkan dalam waktu linier. Ini karena mengenali grafik split dapat dilakukan dalam waktu linier (terkenal).$k=1$
• Untuk , masalahnya adalah NP-complete. Ini dibuktikan oleh Lau dan Corneil dalam Mengakui kekuatan interval, split, dan grafik chordal yang tepat , SIAM J. Discrete Math., 18 (2004), 83-102 .$k=2$
• Untuk , masalahnya adalah sepele: hanya grafik lengkap yang merupakan kekuatan ke- k dari grafik perpecahan.$k\ge 3$$k$

$\Delta$$\Delta=2$3 ⩽ delta ⩽ $\Delta\geqslant 7$$3\leqslant\Delta\leqslant 6$

Pertanyaan terkait dibahas di sini .

Menentukan apakah grafik memiliki klik yang mendominasi untuk:$G$

• $diam(G)=1$ adalah sepele - jawabannya selalu 'ya'
• $diam(G)=2$ adalah NP-complete
• $diam(G)=3$ adalah NP-complete
• $diam(G)\ge 4$ adalah sepele - jawaban selalu 'tidak'

Kasus adalah karena Brandstädt dan Kratsch , dan kasus dicatat dalam makalah saya baru-baru ini .d i a m ( G ) = $diam(G)=3$$diam(G)=2$

Apakah ini contoh dari fenomena yang Anda cari?

Pertimbangkan masalah k-Clique, di mana k adalah ukuran klik yang kita cari. Jadi masalahnya adalah "Apakah ada klik ukuran k dalam grafik G pada n simpul?"

Untuk semua konstanta k, masalahnya adalah dalam P. (Algoritma brute force berjalan dalam waktu .) Untuk nilai-nilai k yang besar, misalnya nilai-nilai seperti n / 2, itu adalah NP-complete. Ketika k menjadi sangat dekat dengan n, seperti nc untuk beberapa konstanta c, masalahnya ada di P lagi karena kita dapat mencari semua himpunan bagian n simpul ukuran nc dan memeriksa apakah ada dari mereka yang membentuk sebuah klik. (Hanya ada himpunan bagian seperti itu, yang secara polinomi besar ketika c adalah konstanta.)O ( n c$O(n^k)$$O(n^c)$

Berikut ini contoh yang mungkin dari jenis yang Anda cari. Parameternya bukan bilangan bulat, melainkan sepasang angka. (Meskipun salah satu dari mereka dapat diperbaiki untuk menjadikannya masalah satu parameter.)

Masalahnya adalah untuk mengevaluasi polinomial Tutte dari grafik G pada koordinat (x, y). Kita dapat membatasi koordinat menjadi bilangan bulat. Masalahnya adalah dalam P jika (x, y) adalah salah satu poin (1, 1), (-1, -1), (0, -1), (-1,0), atau memuaskan (x-1) ) (y-1) = 1. Kalau tidak, itu # P-hard.

Saya mendapatkan ini dari artikel Wikipedia tentang polinomial Tutte .

Bagaimana dengan pertanyaan tentang komputasi modulo permanen ? Untuk ini mudah (karena permanen = determinan), dan Valiant (dalam " Kompleksitas menghitung permanen ") menunjukkan ia dapat dihitung modulo dalam waktu untuk oleh varian modifikasi dari eliminasi Gaussian. Tapi untuk yang bukan kekuatan , itu adalah UP-Hard. k = 2 2 d O ( n 4 d - 3 ) d ≥ 2 k $k$$k=2$$2^d$$O(n^{4d-3})$$d \geq 2$$k$$2$

Masalah lain dengan fenomena ini adalah masalah MINIMUM -SPANNER pada grafik terpisah.$t$

Untuk konstan , -spanner dari graf yang terhubung adalah subgraf spanning terhubung dari sedemikian sehingga untuk setiap pasangan simpul dan , jarak antara dan dalam paling banyak kali jaraknya dalam . Masalah MINIMUM -SPANNER meminta -spanner dengan jumlah tepi minimum dari grafik yang diberikan.$t$$t$H G x y x y H t G t $G$$H$$G$$x$$y$$x$$y$$H$$t$$G$$t$$t$

Sebuah grafik perpecahan adalah grafik yang ditetapkan vertex dapat dipartisi menjadi clique dan set independen.

Dalam tulisan ini ditunjukkan bahwa MINIMUM 2-SPANNER pada grafik split adalah NP-hard sedangkan untuk setiap , MINIMUM -SPANNER mudah pada grafik split.$t \ge 3$$t$

Contoh terkenal adalah pewarnaan -edge.$k$

Diputuskan dalam waktu polinomial jika sebaliknya -complete .N P$k \ne \Delta$$NP$

Untuk grafik kubik, tentukan keberadaan pewarnaan tepi menggunakan:

• $k=2$ warna sepele karena jawabannya selalu tidak.
• N $k=3$ warna adalah -complete$NP$
• $k \ge 4$ warna sepele karena jawaban selalu ya.

Holyer, Ian (1981), "NP-kelengkapan pewarnaan tepi", Jurnal SIAM tentang Komputasi 10: 718-720

http://en.wikipedia.org/wiki/Edge_coloring

Ini adalah contoh yang menarik (dan mengejutkan) untuk transisi fase P NP-hard P NP-hard :$\to$$\to$$\to$$\to \cdots$

Memutuskan apakah grafik lengkap pada simpul, di mana setiap simpul memiliki peringkat ketat dari semua simpul lainnya, mengakui pencocokan populer adalah dalam P untuk aneh dan NP-keras untuk bahkan . (Parameternya adalah nomor simpul .)$n$$n$$n$$n$

Buktinya telah diumumkan dalam makalah ini .

$k$$k$

$G$$k=1$$G$$\sf NP$$k \in \{2,3\}$$\sf P$$k$

Lihat Chandran, L. Sunil, Deepak Rajendraprasad, dan Marek Tesař. "Rainbow Coloring of Splits Graphs." arXiv preprint arXiv: 1404.4478 (2014).

$U\subseteq V(G)$$G$$G[U]$$G-U$

Memutuskan apakah grafik dengan diameter 1 memiliki cutset yang terputus adalah sepele. Masalahnya menjadi NP-keras pada grafik diameter 2 lihat makalah ini dan sekali lagi mudah pada grafik diameter setidaknya 3 melihat makalah ini .