Apa motivasi di balik definisi traktabilitas parameter tetap?

FPT berisi masalah traktable parameter tetap, yang dapat diselesaikan dalam waktu untuk beberapa fungsi yang dapat dihitung . Biasanya, fungsi ini dianggap sebagai eksponensial tunggal, seperti tetapi definisi tersebut mengakui fungsi yang tumbuh lebih cepat. Ini penting untuk sebagian besar sejarah awal kelas ini. Bagian penting dari definisi ini adalah untuk mengecualikan fungsi dari bentuk , seperti $f(k)\cdot|x|^{O(1)}$ $f$ $2^{O(k)}$ $f(n,k)$ $n^k$ .

Pertanyaan : Apa motivasi di balik definisi ini?

Apa yang membingungkan saya adalah bahwa, jika adalah tetap (sesuai "tractability parameter tetap"), maka adalah polinomial dalam . Jadi, mengapa penting untuk mengecualikan ? $k$ $n^k$ $n$ $n^k$

cc.complexity-theory fixed-parameter-tractable Douglas S. Stones
sumber

Karena

sering kedua sepele dari perspektif teori dan terlalu lambat dari perspektif praktis. Salah satu cara untuk mengatakannya adalah bahwa bisnis FPT mencoba memahami kompleksitas komputasi masalah untuk nilai-nilai parameter yang ada di stadion baseball

dan

n^{k}

$n^k$

n \approx 1000000

$n ≈ 1000000$

k \approx 30

$k ≈ 30$

Jukka Suomela

Hmm ... jadi, jika saya mengerti benar, jika kita membiarkan

ke FPT, maka kita akan berakhir termasuk sekelompok masalah keputusan sepele, melalui algoritma brute-force.

n^{k}

$n^k$

Douglas S. Stones

Betul. Tentu saja ada hierarki masalah parameter tetap, dan FPT di bagian bawah. n ^ k ada di atas. Lebih umum, idenya adalah untuk mencoba dan memisahkan pengaruh parameter dan pengaruh

, dan karenanya dua bagian terpisah dari waktu berjalan.

n

$n$

Suresh Venkat

@JukkaSuomela: Saya pikir komentar Anda bisa dijawab.

Suresh Venkat

Jawaban:

Jika Anda hanya menginginkan laju pertumbuhan menjadi polinomial dalam untuk tetap , maka Anda mendapatkan definisi kompleksitas parameterized kelas XP, yang tentunya merupakan objek yang menarik, jadi tidak ada yang salah dengan mempertimbangkannya. $n$ $k$

Anda mendapatkan definisi FPT jika Anda lebih jauh memaksakan kondisi bahwa tingkat polinomial dalam tetap tetap seiring dengan meningkatnya parameter. FPT ternyata menjadi subclass sangat penurut dari XP, dan intuitif, alasannya adalah bahwa ekspresi seperti tidak meledak secepat ekspresi seperti , jika dan adalah baik $n$ $2^k n^2$ $k^2 n^k$ $k$ $n$ meningkat. Intuisi ini didukung dalam praktik dan teori; yaitu, masalah FPT cenderung jauh lebih mudah ditelusuri dalam praktik daripada masalah XP sewenang-wenang, dan orang juga bisa mendapatkan gambaran teoritis yang bagus tentang struktur XP dengan mulai dengan FPT di bagian bawah dan membangun hierarki subkelas XP lainnya (seperti W hierarki) di atasnya.

Timothy Chow
sumber