Contoh pengurangan-FPT yang bukan merupakan pengurangan waktu polinomial

Dalam kompleksitas parametrized orang menggunakan reduksi fixed-parameter-tractable (FPT) untuk membuktikan W [t] -kekerasan. Secara teoritis pengurangan FPT bukan pengurangan waktu polinomial, karena dapat dijalankan secara eksponensial pada parameter k. Tetapi dalam praktiknya semua pengurangan FPT yang saya lihat adalah pengurangan p-time, yang berarti W [t] -kurang bukti hampir selalu menyiratkan bukti kelengkapan NP.

Saya ingin tahu apakah seseorang dapat memberi saya pengurangan FPT yang memang berjalan secara eksponensial di dalam parameter . Terima kasih.$k$

Contoh awal adalah W [2] -kekuatan bukti untuk Tournament Dominating Set (Teorema 4.1 dalam [1]). Pengurangannya dari Dominating Set dan membangun turnamen dengan simpul , di mana n adalah jumlah simpul dari himpunan himpunan yang mendominasi dan k adalah parameternya.$O(2^k n)$$n$$k$

[1]: Rodney G. Downey dan Michael R. Fellows. Kelayakan komputasi parameter. Dalam P. Clote dan JB Remmel, editor, Prosiding Layak Matematika II, halaman 219-244. Birkhauser, 1995.

Makalah berikut berisi reduksi untuk berbagai parameterisasi Closest Substring di mana waktu berjalan tergantung secara eksponensial atau dua kali secara eksponensial pada parameter (dan ketergantungan ini tampaknya tidak dapat dihindari).

D. Marx. Masalah substring terdekat dengan jarak kecil . Jurnal SIAM tentang Komputer, 38 (4): 1382-1410, 2008.

Sebagai pelengkap dari jawaban lain, Proposisi berikut menunjukkan bahwa gagasan terkait redukibilitas tidak dapat dibandingkan:

$(Q,k)$$(Q',k')$$(Q,k) <^{\mathrm{fpt}} (Q',k')$$Q' <^{\mathrm{ptime}}\ Q$

$<^{\mathrm{fpt}}$$<^{\mathrm{ptime}}$

[2]: J. Flum, M. Grohe. Teori Kompleksitas Parameter. Springer (2006)

Mungkin ini bukan jawaban yang dimaksudkan, tetapi bagaimana dengan (varian derandomized) pengkodean warna untuk masalah k-path? http://en.wikipedia.org/wiki/Color-coding

Di sana, seseorang mengubah sebuah instance dari masalah k-path ke instance dari masalah k-path yang penuh warna oleh pengurangan-fpt dengan ketergantungan super-polinomial pada k. (Satu menciptakan banyak contoh, tetapi mereka dapat dilihat sebagai satu contoh besar.) Karena masalah k-path berwarna-warni dapat diselesaikan dalam waktu fpt oleh pemrograman dinamis, kita dapat menyimpulkan masalah k-path milik FPT.

Contoh lain dari pengurangan tersebut adalah bukti kekerasan untuk dimensi VC. Lihat "Kompleksitas pembelajaran parameterized" oleh Downey, Evans dan Fellows.