Czy kompletność PSPACE oznacza twardość aproksymacyjną?

14

W komentarzu w innym poście z cstheorySE wspomniano, że kompletność PSPACE implikuje twardość APX. Czy ktoś może wyjaśnić / udostępnić referencję?

Czy to jest „ciasne”? (tj. czy istnieją problemy kompletne z PSPACE, których problem optymalizacji dopuszcza stałe przybliżanie współczynnika w czasie wielopunktowym?

Co z kompletnością dla pewnego poziomu PH? Czy oznacza to jakąś twardość aproksymacyjną?

cc.complexity-theory approximation-algorithms approximation-hardness np pspace RB
źródło
2
Zobacz arxiv.org/pdf/math/9409225.pdf
Saeed
4
Ten artykuł wydaje się dawać wyniki PTAS dla problemów z PSPACE: cs.albany.edu/~madhav/pubs.d/stoc94.ps
Sasho Nikolov
4
Ugh, to był zły komentarz. Pomysł polegał na zgadywaniu heurystycznym, więc przepraszam, jeśli okazał się faktem! Jeden to klasa problemów decyzyjnych, a drugi to klasa problemów funkcyjnych, więc instrukcja nie jest nawet dobrze zdefiniowana. Myślę, że powodem było to, że możesz odpowiedzieć na problem w APX dokładnie za pomocą przestrzeni wielomianowej. Ale sformalizowanie połączenia wymagałoby trochę pracy i nie miałem na myśli żadnych formalnych wyników, o których wiedziałem.
usul
1
Te dwa pomysły wydają się dość odrębne. Można przypuszczać, że celem funkcja dla większości problemów, może być modyfikowane w celu f ( x ) = f ( x ) + n k , gdzie k jest górną granicą wartości F może przyjmować możliwych rozwiązań. F jest więc wciąż tak trudno dokładnie obliczyć jak F , ale trywialny ma ( 1 - ε ) (lub nawet ( 1 - 1 / n )f(x)f^(x)=f(x)+nkkff^f(1−ϵ)(1−1/n)) algorytm aproksymacyjny, gdy istnieje wykonalne rozwiązanie. Ten argument powinien dotyczyć klas nawet „trudniejszych” niż PSPACE-complete.
Yonatan N
⊆

Odpowiedzi:

2

Ponieważ nie ma jeszcze odpowiedzi, zwracam się do komentarza, Marathe i in. w swoim artykule ICALP93 zdefiniowali niektóre problemy, które są kompletne w PSPACE, ale dopuszczają stałe przybliżenia współczynników, a także zapewniają pewne wyniki niedopuszczalności. W przypadku tego konkretnego pytania rozważmy MAX3SAT, odpowiedni problem decyzyjny jest PSPACE kompletny, nawet jeśli odpowiadający mu wykres SAT ma strukturę hierarchiczną, jak zdefiniowano w ich pracy, ale ten problem ma algorytm gwarancyjny z 2 przybliżeniami w strukturze hierarchicznej.

Saeed
źródło