Misalkan adalah bahasa parameter untuk beberapa alfabet . The -slice dari adalah , himpunan contoh di yang memiliki parameter . Kelas kompleksitas berisi bahasa parameter sehingga untuk setiap , mungkin dengan algoritma yang berbeda dan waktu berjalan polinomial terikat untuk setiap . Setiap bahasa parameter-tetap ada di , dan ada bahasa diΣ k L L k = L ∩ { ( x , k ) ∣ x ∈ Σ ∗ } L k X P L L k ∈ P k k X P X Pyang tidak ada di ; ini adalah Proposisi 27.1.1 dalam buku teks Downey & Fellows 2013.
Namun, tampaknya memiliki struktur nontrivial di luar ini, karena seseorang dapat membuat stratifikasi kelas ini berdasarkan seberapa cepat tingkat polinom yang terikat tumbuh dengan : untuk derajatnya konstan, sedangkan untuk itu bisa tumbuh semena-mena. Downey & Fellows tidak menyebutkan apa pun tentang struktur luar Proposisi 27.1.1, dan diskusi dalam buku teks Flum & Grohe 2006 tidak jauh lebih terperinci. k F P T X P X P
Melanjutkan dari pertanyaan saya sebelumnya. Batasan varian Independent Set? apakah ada nama untuk subclass dari mana jika ada polinomial sehingga setiap instance dalam dapat diputuskan paling banyak langkah?X P L ∈ Q g L ( x , k ) L | x | g L ( k )
Dengan kata lain, kelas ini hanya memungkinkan hingga waktu alih-alih waktu untuk beberapa fungsi sewenang-wenang seperti untuk .| x | poli ( k ) | x | g ( k ) g X P
sumber
Jawaban:
Saya tidak berpikir subclass ini telah dipelajari dalam literatur (dan diberi nama).XP
Salah satu alasan mengapa para peneliti mungkin menghindar untuk mempelajari subkelas ini, adalah karena ia tidak ditutup dengan pengurangan fpt (dan karenanya seseorang harus berurusan dengan pengurangan jenis baru yang 'menjengkelkan'). Ini karena pengurangan-fpt memungkinkan nilai parameter meledak secara superpolynomially (selama itu dibatasi oleh beberapa fungsi yang dapat dihitung dari nilai parameter yang lama). Untuk mendapatkan gagasan pembatasan reduksi fpt di mana subclass ditutup, Anda perlu menambahkan batasan bahwa pengurangan fpt memerlukan nilai parameter baru untuk dibatasi oleh beberapa polinomial dari nilai parameter lama.XP
sumber