Dugaan: Semua bahasa FPT NP-lengkap adalah fixed-parameter-isomorphic

10

Dugaan Berman-Hartmanis: semua bahasa NP-lengkap terlihat sama, dalam arti bahwa mereka dapat saling terkait oleh isomorfisme waktu polinomial [1].

Saya tertarik pada versi "polinomial time" yang lebih berbutir halus, yaitu, jika kita menggunakan pengurangan parameter.

Masalah parameter adalah himpunan bagian dari , di mana adalah alfabet terbatas dan adalah himpunan bilangan non-negatif. Sebuah instance dari masalah parameterized karena itu adalah pasangan , di mana adalah parameternya.(I,k)kΣ×Z0 Z 0ΣZ0(I,k)k

Masalah parameter adalah parameter tetap direduksi menjadi masalah parameter jika ada fungsi , : , dan polinomial seperti bahwa untuk setiap instance dari , adalah turunan dari dapat dihitung dalam waktu dan jika dan hanya jika . Dua masalah yang diparameterisasi adalah parameter-tetap yang setara jika keduanya merupakan parameter-tetap yang dapat direduksi satu sama lain.π 2 fgZ0Z0 Φ : Σ *×Z0 Σ * p(·)(I,k) π 1 ( Φ (I,k),g(k)) π 2 f(k)·p( | I | )π1π2fgZ0Z0Φ:Σ×Z0Σp(·)(I,k)π1(Φ(I,k),g(k))π2f(k)·p(|I|) ( Φ ( I , k ) , g ( k ) ) π 2(I,k)π1(Φ(I,k),g(k))π2

Beberapa masalah NP-complete adalah FPT, misalnya, versi keputusan dari masalah vertex cover adalah NP-Complete, ia memiliki algoritma [2]. Menemukan pengurangan parameter-tetap yang lebih baik dari masalah FPT yang NP-Lengkap dapat mengarah pada algoritma yang lebih baik, misalnya, dengan menerapkan pengurangan ke "versi jaminan di atas" dari masalah Multiway Cut yang dapat mengarah pada suatu algoritma dalam waktu untuk masalah AGVC (Above Guarantee Vertex Cover) [3], yang lebih baik daripada algoritma [4].O ( 4 k ) O ( 15 k )O(1.2738k+kn)O(4k)O(15k)

My Conjecture: All FPT NP-complete languages are fixed-parameter-isomorphic.

Apakah dugaan itu benar?

[1] Berman, L .; Hartmanis, J. (1977), "Tentang isomorfisma dan kepadatan NP dan set lengkap lainnya", SIAM Journal on Computing 6 (2): 305-322.

[2] J. Chen, IA Kanj, dan G. Xia, Peningkatan batas atas untuk penutup simpul, Theor.Comput. Sci., 411 (2010), hlm. 3736-3756.

[3] M. Cygan, M. Pilipczuk, M. Pilipczuk, dan JO Wojtaszczyk, Pada pemotongan multi-jalur parameter di atas batas bawah, dalam IPEC, 2011.

[4] M. Mahajan dan V. Raman, Parameterisasi nilai-nilai dijamin di atas: Maxsat dan maxcut, J. Algoritma, 31 (1999), hlm. 335-354.

Rupei Xu
sumber
3
Saya tidak mengerti apa yang Anda maksud dengan "Bahasa lengkap FPT NP". Tidak ada gagasan alami tentang bahasa dengan sendirinya menjadi FPT; pertanyaannya adalah apakah pasangan bahasa / parameter adalah FPT.
Huck Bennett
4
Perhatikan bahwa pengurangan parameter-tetap hanya bisa menyelesaikan masalah FPT, dan mengeluarkan contoh Ya / Tidak yang sepele dari masalah target.
Serge Gaspers

Jawaban:

7

Serge Gaspers sudah menyebutkan mengapa dugaan Anda sepele.
Namun, orang sebenarnya bisa mendapatkan isomorfisme parameter waktu tetap polinomial-waktu ,
yang sekarang saya sadari tidak terlalu sepele, karena berlaku untuk setiap
pasangan terurut masalah FPT non-sepele dengan pengurangan dalam pengertian biasa.


Biarkan menjadi bilangan bulat yang lebih besar daripada derajat algoritma FPT untuk , dan biarkan dan menjadi masing-masing ya dan tidak ada contoh dari . Berikut ini adalah pengurangan parameter -waktu tetap polinomial dari ke :π 1 Y N π 2 π 1 π 2cπ1
YNπ2
π1π2

Coba algoritma FPT pada untuk hingga langkah. Jika itu memberikan jawaban, maka output atau seperti yang ditunjukkan oleh jawaban itu. Jika tidak, output hasil menerapkan pengurangan waktu polinomial biasa dari ke . Kebenaran dan runtime polinom jelas. Karena lebih besar dari derajat algoritma FPT untuk , maka untuk setiap tetap , hanya ada banyak panjang input yang runtime maksimum algoritma FPT tidak kurang darinπ1 YN π 1 π 2nc
YN
π1π2


π 1 k n ncπ1knnc . Jadi, untuk setiap tetap , reduksi di atas hanya memiliki banyak keluaran. Karena itu memenuhi kondisi parameter tetap Anda.k


sumber