Apakah Ada Masalah Lengkap PSPACE tertentu yang memiliki algoritma FPTAS?

Diketahui bahwa NP-Complete Problem yang disebut Subset Sum memiliki FPTAS. Saya bertanya-tanya apakah ada masalah Lengkap PSPACE yang juga memiliki FPTAS? Terima kasih sebelumnya.

ds.algorithms space-bounded big-picture Zelah 02
sumber

Saya kira jawabannya adalah tidak. 3-partisi tidak menerima FPTAS karena ini sangat lengkap NP kecuali P = NP. Juga, ada pengurangan Karp dari 3-partisi ke masalah persaingan PSPACE. Oleh karena itu, FPTAS untuk setiap masalah PSPACE-lengkap akan menyiratkan FPTAS untuk 3-partisi yang tidak mungkin kecuali P = NP.

Mohammad Al-Turkistany

Reduksi karp adalah perkiraan reduksi pelestarian.

Mohammad Al-Turkistany

Saya tidak mengerti - mengapa pengurangan perkiraan Karp dipertahankan?

Peter Shor

Reduksi karp didefinisikan untuk masalah keputusan, salah satu dari pengurangan yang mempertahankan perkiraan didefinisikan untuk masalah optimasi. Oleh karena itu, pengurangan Karp tidak bisa menjadi pengurangan yang mempertahankan perkiraan.

Oleksandr Bondarenko

@Oleksandr, Lihatlah ini ( cs.tau.ac.il/~safra/Complexity/PCP.pdf )

Mohammad Al-Turkistany

Jawaban:

Dimungkinkan untuk mendefinisikan masalah PSPACE-HARD buatan dengan FPTAS: define di mana adalah masalah Boolean PSPACE-keras yang kompleksitas adalah paling , maka juga PSPACE-keras, tetapi memiliki FPTAS: jika lalu kembalikan kalau tidak kita punya cukup waktu untuk menghitung tepat. $f(x)=2^{|x|}+g(x)$ $g(x)$ $2^n$ $f$ $\epsilon \gt 2^{-|x|}$ $2^{|x|}$ $f$

Noam
sumber

Bisakah Anda memberikan masalah khusus hard-PSPACE (lebih disukai natural) dengan kompleksitas waktu

O (2^{n})

$O(2^n)$

Mohammad Al-Turkistany

TQBF akan melakukan trik - input: rumus boolean f, output: apakah ada x1 sehingga untuk semua x2 ada x3 sehingga untuk semua x4 ada ... ada xn sedemikian rupa sehingga f (x1 .... xn).

Noam