La complétude de PSPACE implique-t-elle une dureté d'approximation?

14

Il est mentionné dans un commentaire dans un autre article de cstheorySE que PSPACE- exhausteness implique APX-hardness. Quelqu'un peut-il expliquer / partager une référence pour cela?

Est-ce "serré"? (c.-à-d. y a-t-il des problèmes PSPACE complets dont le problème d'optimisation admet une approximation constante des facteurs en temps poly?)

Qu'en est-il de l'exhaustivité pour un certain niveau de PH? Cela implique-t-il une dureté d'approximation?

cc.complexity-theory approximation-algorithms approximation-hardness np pspace RB
la source
2
Voir arxiv.org/pdf/math/9409225.pdf
Saeed
4
Ce document semble donner des résultats PTAS pour les problèmes PSPACE-complete: cs.albany.edu/~madhav/pubs.d/stoc94.ps
Sasho Nikolov
4
Ugh, c'était un mauvais commentaire. L'idée était de faire une supposition heuristique, donc désolé si cela apparaît comme une déclaration de fait! L'un est une classe de problèmes de décision et l'autre est une classe de problèmes de fonction, donc l'énoncé n'est même pas bien défini. Je pense que le raisonnement était simplement que vous pouvez répondre à un problème dans APX en utilisant exactement l'espace polynomial. Mais il faudrait du travail pour formaliser la connexion et je ne faisais référence à aucun résultat formel que je connaissais.
usul
1
F(X)F^(X)=F(X)+nkkFF^F(1-ϵ)(1-1/n)) algorithme d'approximation lorsqu'il existe une solution réalisable. Cet argument devrait tenir pour des classes encore plus "dures" que PSPACE-complete.
Yonatan N
⊆

Réponses:

2

Comme il n'y a pas encore de réponse, je tourne mon commentaire pour répondre, Marathe et al. dans leur article ICALP93 , défini certains problèmes qui sont PSPACE complet mais ils admettent des approximations de facteur constant, ils fournissent également des résultats d'inapproximabilité. Pour cette question particulière, considérons MAX3SAT, le problème de décision correspondant est PSPACE-complet même si le graphe SAT correspondant a une structure hiérarchique telle que définie dans leur article, mais ce problème a un algorithme de garantie d'approximation 2 dans la structure hiérarchique.

Saeed
la source