Konsekuensi dari algoritma distilasi untuk PSPACE

Gagasan algoritma distilasi berikut berasal dari "Pada Masalah Tanpa Kernel Polinomial".

Biarkan bahasa diberikan. Sebuah algoritma destilasi untuk L mengambil daftar yang diberikan string masukan { x i } i ∈ [ t ] dan menghitung output string yang y sehingga:$L$$L$$\{ x_i \}_{i \in [t]}$$y$

(1) jika dan hanya jika ada i ∈ [ t ] sedemikian rupa sehingga x i ∈ $y \in L$$i \in [t]$$x_i \in L$

(2) untuk beberapa polinomial $\vert y \vert \leq p(Max_{i\in[t]} \vert x_i \vert)$$p$

(3) Algoritma menghitung dalam waktu maksimal q ( ∑ i ∈ [ t ] | x i | ) untuk beberapa q polinomial$y$$q(\sum_{i\in[t]}\vert x_i \vert)$$q$

Telah ditunjukkan bahwa jika ada algoritma distilasi untuk masalah -complete, maka c o N P ⊆ N P / p o l y . Selain itu, P H = Σ 3 .$NP$$coNP \subseteq NP/poly$$PH = \Sigma_3$

Lihat detail dan diskusi di:

• "Infeasibility dari Instance Compression dan PCPs ringkas untuk NP"
• "Tentang Masalah Tanpa Biji Polinomial"
• "Batas bawah pada kernelisasi"

Pertanyaan:

• Bisa terdapat algoritma distilasi untuk masalah -Lengkap?$PSPACE$
• Jika algoritma semacam itu ada, konsekuensi kompleksitas apa yang akan kita dapatkan?

Teorema 15.3 dari buku teks "Parameterized Algorithms" baru-baru ini oleh Cygan et al. menyatakan sebagai berikut:

$L, R ⊆ \Sigma^*$$L\in coNP / poly$

$L$$PSPACE \subseteq coNP/poly$