Означает ли PSPACE-полнота твердость аппроксимации?

14

В другом посте cstheorySE упоминается, что PSPACE-полнота подразумевает APX-жесткость. Кто-нибудь может объяснить / поделиться ссылкой на это?

Это "плотно"? (т. е. существуют ли PSPACE-полные задачи, задача оптимизации которых допускает постоянную аппроксимацию множителя за много времени?)

Как насчет полноты для некоторого уровня PH? Означает ли это приблизительную твердость?

cc.complexity-theory approximation-algorithms approximation-hardness np pspace RB
источник
2
См. Arxiv.org/pdf/math/9409225.pdf
Saeed
4
Эта статья, кажется, дает результаты PTAS для задач, завершенных PSPACE: cs.albany.edu/~madhav/pubs.d/stoc94.ps
Сашо Николов
4
Тьфу, это был плохой комментарий. Идея заключалась в том, чтобы сделать эвристическое предположение, так что извините, если это прозвучало как констатация факта! Один - это класс проблем принятия решений, а другой - класс проблем функций, поэтому утверждение даже не является четко определенным. Я думаю, что причина была в том, что вы можете ответить на проблему в APX, используя полиномиальное пространство. Но потребовалась бы некоторая работа, чтобы формализовать связь, и я не имел в виду какие-либо формальные результаты, о которых я знал.
Усул
1
е(Икс)е^(Икс)знак равное(Икс)+NККее^е(1-ε)(1-1/N)) алгоритм приближения, когда есть реальное решение. Этот аргумент должен сохраняться для классов даже «сложнее», чем PSPACE-complete.
Йонатан Н
⊆

Ответы:

2

Поскольку ответа пока нет, я перехожу к комментарию, чтобы ответить, Marathe et al. в их документе ICALP93 определены некоторые задачи, которые являются полными PSPACE, но они допускают приближения с постоянными множителями, они также дают некоторые результаты неприемлемости. Для этого конкретного вопроса рассмотрим MAX3SAT, соответствующая задача решения является PSPACE-полной, даже если соответствующий граф SAT имеет иерархическую структуру, как они определены в их статье, но эта задача имеет алгоритм гарантии 2-аппроксимации в иерархической структуре.

Saeed
источник