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

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

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

cc.complexity-theory np-hardness nondeterminism np-intermediate Абузер Якарылмаз
источник

Ответы:

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

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

Марцио де Биаси
источник

Спасибо! Есть ли у вас какие-либо представления о полилогарифмическом пространстве?

Абузер Якарылмаз

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

domotorp
источник

Спасибо! Есть ли у вас какие-либо представления о полилогарифмическом пространстве?

Абузер Якарылмаз

просто добавить 3CNF с нулями?

2^{\sqrt{n}}

$2^{\sqrt{n}}$

Сашо Николов

@Sasho: Тогда проблема перестанет быть NP-полной, вы можете только PAD с поли числом нулей.

Домоторп

@Abuzer: Я думаю, что пространство для полулогов означает, что NP является частью DTIME [ ]. Это открыто и маловероятно.

2^{p o l y - l o g}

$2^{poly-log}$

Домоторп

@domotorp: Да, вы правы! Спасибо!

Абузер Якарылмаз

Для любого языка в существует доказательство, которое можно проверить с помощью рабочего пространства . Нужно просто использовать те же идеи, которые использовались для доказательства того, что SAT является -complete. По определению, дается языка , мы знаем , что существует машина Тьюринга такая , что для любого существует такой , что принимает. Мы можем построить проверяемое доказательство пространства журналов для , записав и таблицу вычислений на входе $\mathsf{NP}$ $O(\log n)$ $\mathsf{NP}$ $\mathsf{NP}$ $L$ $M$ $x \in L$ $y$ $M(x, y)$ $x$ $y$ $M$ $x, y$ , В пространстве журналов легко проверить, что таблица описывает допустимые вычисления принятия . Точно так же для любого и любого , допустимые вычисления принимаются, поэтому верификатор пространства журналов не будет принимать никаких таблиц. $M$ $x \not \in L$ $y$ $M(x, y)$

Конечно, это не показывает, что (потому что это подразумевает ). Причина в том, что верификатор имеет двусторонний доступ к доказательству (может идти вперед и назад). Определение для средства проверки правописания дает верификатору пространства журнала только односторонний доступ к доказательству (после прочтения части доказательства и перемещения головы вправо она не может двигаться влево). $\mathsf{NP} = \mathsf{NL}$ $\mathsf{NP} = \mathsf{P}$ $\mathsf{NL}$

Сашо Николов
источник

Я не понимаю идею! Вы имеете в виду вероятностную проверку? Если это так, то для любого языка в NP достаточно константного пространства, поскольку . Или вы имеете в виду сокращение пространства журнала любого языка в NP до SAT? Я действительно смущен!

D S P A C E (2^{n}) \subseteq I P (1)

$DSPACE(2^n) \subseteq IP(1)$

Абузер Якарылмаз

Позвольте мне попробовать другой способ: один стандартный способ определения - это класс языков, которые имеют детерминированные верификаторы многократного использования. Я говорю, что эквивалентным определением является определение как класса языков, которые имеют детерминированные верификаторы пространства журналов с множественным доступом для чтения к доказательству. случайность не нужна.

N P

$\mathsf{NP}$

N P

$\mathsf{NP}$

Сашо Николов

Спасибо. На самом деле я это знал :) класс пространства журнала, основанный на вашем объяснении, обозначается как , и да, . Кроме того, . Понятия «оффлайн» и «онлайн», как вы указали, представляют типы доступа к данному доказательству. REF: раздел 5.3.1 «Вычислительная сложность» Одеда Голдрайха (2008).

N S P A C E_{o f f - l i n e} (l o g)

$\mathsf{NSPACE_{off\mbox{-}line}(log)}$

N P = N S P A C E_{o f f - l i n e} (l o g)

$\mathsf{NP} = \mathsf{NSPACE_{off\mbox{-}line}(log)}$

N L = N S P A C E_{o n - l i n e} (l o g)

$\mathsf{NL} = \mathsf{NSPACE_{on\mbox{-}line}(log)}$

Абузер Якарылмаз