Существует ли конкретная проблема завершения PSPACE с алгоритмом FPTAS?

Хорошо известно, что задача NP-Complete, называемая Subset Sum, имеет FPTAS. Мне было интересно, если существует проблема PSPACE Complete, которая также имеет FPTAS? Заранее спасибо.

ds.algorithms space-bounded big-picture Зелах 02
источник

Я думаю, что ответ будет нет. 3-разделение не допускает FPTAS, так как оно сильно NP-завершено, если P = NP. Кроме того, есть сокращение Карпа с 3-х разделов до любой проблемы, связанной с PSPACE. Следовательно, FPTAS для любой задачи, полной PSPACE, подразумевает FPTAS для 3-разделов, что невозможно, если P = NP.

Мухаммед Аль-Туркистани

Редукция Карпа является приближением, сохраняющим аппроксимацию.

Мухаммед Аль-Туркистани

Я не понимаю - почему сохранение карповой аппроксимации сохраняет?

Питер Шор

Редукция Карпа определена для задач решения, любая из сокращений, сохраняющих приближение, определена для задач оптимизации. Следовательно, уменьшение Карпа не может быть сохранением аппроксимации.

Александр Бондаренко

@ Александр, посмотрите на это ( cs.tau.ac.il/~safra/Complexity/PCP.pdf )

Мухаммед Аль-Туркистани

Ответы:

С помощью FPTAS можно определить искусственные задачи PSPACE-HARD: define где - булева задача, сложная для PSPACE, сложность которой не больше , тогда также PSPACE-сложный, но имеет FPTAS: если то вернуть иначе у нас будет достаточно времени для точного вычисления . $f(x)=2^{|x|}+g(x)$ $g(x)$ $2^n$ $f$ $\epsilon \gt 2^{-|x|}$ $2^{|x|}$ $f$

Ноам
источник

Не могли бы вы дать конкретную (желательно естественную) сложную задачу PSPACE с сложностью по времени?

O (2^{n})

$O(2^n)$

Мухаммед Аль-Туркистани

TQBF сделал бы трюк - вход: логическая формула f, вывод: существует ли x1 такой, что для всех x2 существует x3, для всех x4 существует ... существует xn такой, что f (x1 .... xn).

Noam