Apakah kelengkapan PSPACE menyiratkan kekerasan perkiraan?

14

Disebutkan dalam komentar di postingan lain bahwa kelengkapan PSPACE menyiratkan kekerasan APX. Adakah yang bisa menjelaskan / berbagi referensi untuk itu?

Apakah ini "ketat"? (yaitu, apakah ada masalah PSPACE-complete yang masalah optimasi mengakui perkiraan faktor konstan dalam waktu poli?)

Bagaimana dengan kelengkapan untuk beberapa level PH? Apakah itu menyiratkan kekerasan perkiraan?

cc.complexity-theory approximation-algorithms approximation-hardness np pspace BPR
sumber
2
Lihat arxiv.org/pdf/math/9409225.pdf
Saeed
4
Makalah ini tampaknya memberikan hasil PTAS untuk masalah lengkap PSPACE: cs.albany.edu/~madhav/pubs.d/stoc94.ps
Sasho Nikolov
4
Ugh, itu komentar yang buruk. Idenya adalah untuk membuat perkiraan heuristik, sangat menyesal jika itu muncul sebagai pernyataan fakta! Satu adalah kelas masalah keputusan dan satu adalah kelas masalah fungsi, jadi pernyataan itu bahkan tidak didefinisikan dengan baik. Saya pikir alasannya hanya bahwa Anda dapat menjawab masalah di APX persis menggunakan ruang polinomial. Tetapi perlu beberapa usaha untuk meresmikan koneksi dan saya tidak merujuk pada hasil formal yang saya tahu.
usul
1
Kedua gagasan itu tampak agak berbeda. Agaknya, fungsi objektif untuk sebagian besar masalah dapat dimodifikasi menjadi mana adalah batas atas pada nilaif(x)f^(x)=f(x)+nkkf can take on feasible solutions. f^ is then still just as hard to compute exactly as is f, but it trivially has a (1−ϵ) (or even (1−1/n)) approximation algorithm when there's a feasible solution. This argument should hold for classes even "harder" than PSPACE-complete.
Yonatan N
If I remembered it correctly, APX are just defined for NP optimization problems? i.e., APX ⊆ NP-optimization. When we talk about PSPACE-Complete, aren't we already beyond the regime of the definition?
Stupid_Guy

Jawaban:

2

Karena belum ada jawaban, saya mengalihkan komentar saya untuk menjawab, Marathe et al. dalam makalah ICALP93 mereka , mendefinisikan beberapa masalah yang selesai PSPACE tetapi mereka mengakui perkiraan faktor konstan, mereka juga memberikan beberapa hasil yang tidak dapat diperkirakan. Untuk pertanyaan khusus ini, pertimbangkan MAX3SAT, masalah keputusan yang sesuai adalah PSPACE-complete bahkan jika grafik SAT yang sesuai memiliki struktur hierarkis seperti yang didefinisikan dalam makalah mereka, tetapi masalah ini memiliki algoritme penjaminan 2-perkiraan dalam struktur hierarkis.

Saeed
sumber