Существует ли какая-либо известная проблема NP-Complete (или NP-Intermediate) в сублинейном недетерминированном пространстве?

9

Есть некоторые проблемы NP-Complete ( , \ mathsf {SUBSETSUM} и т. Д.), О которых известно, что они находятся в \ mathsf {DSPACE (n)} . Как насчет сублинейных пространств?SATSUBSETSUMDSPACE(n)

Существует ли какая-либо известная проблема NP-Complete (или NP-Intermediate) в сублинейном недетерминированном пространстве?

Абузер Якарылмаз
источник

Ответы:

14

Планарная версия многих NP-полных задач принадлежит NTISP (n, n ^ q)NTISP(n,nq) для некоторых q<1

См., Например, « Нижние оценки и полные задачи в недетерминированных линейных классах сложности времени и сублинейного пространства » П. Шапделейна и Э. Гранджина (2006)

Марцио де Биаси
источник
Спасибо! Есть ли у вас какие-либо представления о полилогарифмическом пространстве?
Абузер Якарылмаз
14

У любой проблемы есть такая версия, просто изобразите! Например, язык, который состоит из истинного 3CNF длины m, за которым следуют m ^ 2 0, находится в DSPACE (sqrt (n)).

domotorp
источник
Спасибо! Есть ли у вас какие-либо представления о полилогарифмическом пространстве?
Абузер Якарылмаз
1
просто добавить 3CNF с нулями? 2n
Сашо Николов
2
@Sasho: Тогда проблема перестанет быть NP-полной, вы можете только PAD с поли числом нулей.
Домоторп
1
@Abuzer: Я думаю, что пространство для полулогов означает, что NP является частью DTIME [ ]. Это открыто и маловероятно. 2polylog
Домоторп
@domotorp: Да, вы правы! Спасибо!
Абузер Якарылмаз
11

Для любого языка в существует доказательство, которое можно проверить с помощью рабочего пространства . Нужно просто использовать те же идеи, которые использовались для доказательства того, что SAT является -complete. По определению, дается языка , мы знаем , что существует машина Тьюринга такая , что для любого существует такой , что принимает. Мы можем построить проверяемое доказательство пространства журналов для , записав и таблицу вычислений на входеNPO(logn)NPNPLMxLyM(x,y)xyMx,y, В пространстве журналов легко проверить, что таблица описывает допустимые вычисления принятия . Точно так же для любого и любого , допустимые вычисления принимаются, поэтому верификатор пространства журналов не будет принимать никаких таблиц.MxLyM(x,y)

Конечно, это не показывает, что (потому что это подразумевает ). Причина в том, что верификатор имеет двусторонний доступ к доказательству (может идти вперед и назад). Определение для средства проверки правописания дает верификатору пространства журнала только односторонний доступ к доказательству (после прочтения части доказательства и перемещения головы вправо она не может двигаться влево).NP=NLNP=PNL

Сашо Николов
источник
Я не понимаю идею! Вы имеете в виду вероятностную проверку? Если это так, то для любого языка в NP достаточно константного пространства, поскольку . Или вы имеете в виду сокращение пространства журнала любого языка в NP до SAT? Я действительно смущен! DSPACE(2n)IP(1)
Абузер Якарылмаз
1
Позвольте мне попробовать другой способ: один стандартный способ определения - это класс языков, которые имеют детерминированные верификаторы многократного использования. Я говорю, что эквивалентным определением является определение как класса языков, которые имеют детерминированные верификаторы пространства журналов с множественным доступом для чтения к доказательству. случайность не нужна. NPNP
Сашо Николов
4
Спасибо. На самом деле я это знал :) класс пространства журнала, основанный на вашем объяснении, обозначается как , и да, . Кроме того, . Понятия «оффлайн» и «онлайн», как вы указали, представляют типы доступа к данному доказательству. REF: раздел 5.3.1 «Вычислительная сложность» Одеда Голдрайха (2008). NSPACEoff-line(log)NP=NSPACEoff-line(log)NL=NSPACEon-line(log)
Абузер Якарылмаз