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

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ą?

— RB
źródło

Zobacz arxiv.org/pdf/math/9409225.pdf

— Saeed

Ten artykuł wydaje się dawać wyniki PTAS dla problemów z PSPACE: cs.albany.edu/~madhav/pubs.d/stoc94.ps

— Sasho Nikolov

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

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

, gdzie

jest górną granicą wartości

może przyjmować możliwych rozwiązań.

jest więc wciąż tak trudno dokładnie obliczyć jak

, ale trywialny ma

(lub nawet

f (x)

$f(x)$

\hat{f} (x) = f (x) + n k

$\hat{f}(x) = f(x) + nk$

k

$k$

f

$f$

\hat{f}

$\hat{f}$

f

$f$

(1 - ϵ)

$(1-\epsilon)$

(1 - 1 / n)

$(1-1/n)$ ) algorytm aproksymacyjny, gdy istnieje wykonalne rozwiązanie. Ten argument powinien dotyczyć klas nawet „trudniejszych” niż PSPACE-complete.

— Yonatan N

\subseteq

$\subseteq$

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