Mengapa semua masalah di FPTAS juga ada di FPT?

Menurut artikel Wikipedia tentang skema perkiraan polinomial-waktu :

Semua masalah dalam FPTAS adalah traktat parameter tetap.

Hasil ini mengejutkan saya - kelas-kelas ini tampaknya sangat berbeda satu sama lain. FPTAS mengkarakterisasi masalah dengan seberapa mudah mereka memperkirakan, sementara FPT mengkarakterisasi masalah dengan kesulitan mereka relatif terhadap beberapa parameter. Sayangnya, Wikipedia (pada saat saya mengajukan pertanyaan ini) tidak memberikan kutipan untuk ini.

Apakah ada bukti standar dari hasil ini? Atau adakah sumber yang bisa saya hubungi untuk mempelajari lebih lanjut tentang koneksi ini?

Sebenarnya ada hasil yang lebih kuat; Masalahnya ada di kelas jika memiliki fptas ¹ : an -approximation berjalan dalam waktu yang dibatasi oleh (yaitu polinomial dalam ukuran dan faktor aproksimasi). Ada kelas yang lebih umum yang melemaskan batas waktu untuk - pada dasarnya adalah -seperti waktu berjalan sehubungan dengan faktor aproksimasi. ε ( n + $\mathrm{FPTAS}$$\varepsilon$EPTASf($(n+\frac{1}{\varepsilon})^{\mathcal{O}(1)}$$\mathrm{EPTAS}$FP$f(\frac{1}{\varepsilon})\cdot n^{\mathcal{O}(1)}$$\mathrm{FPT}$

Jelas adalah himpunan bagian dari E P T A S , dan ternyata E P T A S adalah himpunan bagian dari F P T dalam pengertian berikut:$\mathrm{FPTAS}$$\mathrm{EPTAS}$$\mathrm{EPTAS}$$\mathrm{FPT}$

Teorema Jika masalah NPO memiliki$\Pi$ eptas, maka diparameterisasi dengan biaya solusi adalah parameter tetap yang dapat ditelusur.$\Pi$

Teorema dan bukti diberikan dalam Flum & Grohe [1] sebagai Teorema 1.32 (hal. 23-24), dan mereka mengaitkannya dengan Bazgan [2], yang menempatkannya dua tahun sebelum hasil Cai & Chen yang lebih lemah (tetapi dalam bahasa Prancis laporan teknikal).

Saya akan memberikan sketsa buktinya, karena saya pikir itu adalah bukti teorema yang bagus. Untuk mempermudah saya akan melakukan versi minimalisasi, cukup lakukan inversi yang sesuai secara mental untuk maksimalisasi.

Bukti. Misalkan menjadi eptas untuk Π , maka kita dapat membuat algoritme parameterisasi A ′ untuk Π yang diparameterisasi dengan biaya solusi k sebagai berikut: diberi input ( x , k ) , kita menjalankan A pada input x di mana kita menetapkan ε : = $A$$\Pi$$A'$$\Pi$$k$$(x,k)$$A$$x$ (yaitu kita memilih rasio aproksimasi terikat1+$\varepsilon := \frac{1}{k+1}$ ). Biarkanymenjadi solusinya,biaya(x,y)menjadi biayaydanr(x,y)menjadi rasio perkiraan aktual dariyuntukmemilih(x), yaitubiaya(x,y)=r(x,y)⋅opt(x).$1+\frac{1}{k+1}$$y$$\text{cost}(x,y)$$y$$r(x,y)$$y$$\text{opt}(x)$$\text{cost}(x,y) = r(x,y)\cdot \text{opt}(x)$

Jika , maka terima, dengan jelas memilih ( x ) ≤ biaya ( x , y ) ≤ k . Jika biaya ( x , y ) > k , tolak sebagai r ( x , y ) ≤ 1 + $\text{cost}(x,y) \leq k$$\text{opt}(x) \leq \text{cost}(x,y) \leq k$$\text{cost}(x,y) > k$ sebagaiAadalaheptasdan$r(x,y) \leq 1+\frac{1}{k+1}$$A$

Tentu saja Anda mendapatkan batas waktu berjalan untuk hanya dari A menjadi epta . $A'$$A$$\Box$

Tentu saja sebagai poin Pål keluar, hasil kekerasan diparameterkan menyiratkan tidak adanya dari setiap eptas kecuali ada beberapa runtuh, tetapi ada masalah di tanpa eptas (atau bahkan POMG ), sehingga E P T A S adalah ketat subset dari F P T (dalam arti teorema).$\mathrm{FPT}$$\mathrm{EPTAS}$$\mathrm{FPT}$

Catatan kaki:

1. Sebuah fptas (ekuivalen eptas atau POMG ) adalah skema pendekatan dengan waktu berjalan dibatasi seperti dijelaskan di atas. The kelas (equiv. E P T A S , P T A S ) adalah serangkaian masalah di N P O yang memiliki skema tersebut.$\mathrm{FPTAS}$$\mathrm{EPTAS}$$\mathrm{PTAS}$$\mathrm{NPO}$

[1]: J. Flum dan M. Grohe, Teori Kompleksitas Parameter , Springer, 2006.
[2]: C. Bazgan. Schémas d'approximation et complexité paramétrée , Rapport de DEA, Université Paris Sud, 1995.