NC = P последствия?

Сложность Zoo указывает в записи на EXP, что если L = P, то PSPACE = EXP. Поскольку NPSPACE = PSPACE от Savitch, насколько я могу судить, нижележащий аргумент отступа расширяется, чтобы показать, что Мы также знаем, что L NL NC P через ограниченную по ресурсам чередующуюся иерархию.

(NL = P) \Rightarrow (PSPACE = EXP) .

$(\text{NL} = \text{P}) \Rightarrow (\text{PSPACE} = \text{EXP}).$

\subseteq

$\subseteq$

\subseteq

$\subseteq$

\subseteq

$\subseteq$

Если NC = P, следует ли это, что PSPACE = EXP?

Другая интерпретация вопроса в духе Ричарда Липтона: более вероятно, что некоторые задачи в P не могут быть распараллелены, чем то, что никакая процедура по экспоненциальному времени не требует большего, чем полиномиальное пространство?

Меня также интересовали бы другие «удивительные» последствия NC = P (чем меньше вероятность, тем лучше).

Редактировать: ответ Райана приводит к дальнейшему вопросу: какая самая слабая гипотеза, которая, как известно, гарантирует PSPACE = EXP?

В. Савич. Взаимосвязь между недетерминированными и детерминированными сложностями ленты, Журнал компьютерных и системных наук 4 (2): 177-192, 1970.
WL Ruzzo. О сложности единой схемы, Журнал компьютерных и системных наук 22 (3): 365-383, 1971.

Edit (2014): обновлена старая ссылка Zoo и добавлены ссылки для всех других классов.

cc.complexity-theory conditional-results Андраш Саламон
источник

Я уверен, что я не единственный, кто не знает, что такое NC, вот ссылка: en.wikipedia.org/wiki/NC_%28complexity%29

Эмиль

@Andras: Еще одно следствие, которое, возможно, вы уже знаете, но еще не было упомянуто, заключается в том, что иерархия рухнет, поскольку имеет полные проблемы при -reductions ,

N C

$\mathsf{NC}$

P

$\mathsf{P}$

L

$\mathsf{L}$

Джошуа

Ответы:

Да. можно рассматривать как класс языков, распознаваемых чередующимися машинами Тьюринга, которые используют пространство и время. (Это было впервые доказано Руццо.) - это класс, в котором чередующиеся машины Тьюринга используют пространство но могут занимать до времени. Для краткости назовем эти классы и . $NC$ $O(\log n)$ $(\log n)^{O(1)}$ $P$ $O(\log n)$ $n^{O(1)}$ $ATISP[(\log n)^{O(1)},\log n] = NC$ $ASPACE[O(\log n)] = P$

Предположим, что два класса равны. Заменив на в приведенном выше (т.е. применяя стандартные леммы перевода), получим $n$ $2^n$

$TIME[2^{O(n)}] = ASPACE[O(n)] = ATISP[n^{O(1)}, n] \subseteq ATIME[n^{O(1)}] = PSPACE$ .

Если тогда , так как в есть языки, полные . $TIME[2^{O(n)}] \subseteq PSPACE$ $EXP = PSPACE$ $EXP$ $TIME[2^{O(n)}]$

Изменить: Хотя приведенный выше ответ, возможно, более образовательный, вот более простой аргумент: уже следует из " содержится в пространстве полилога" и стандартного перевода. Примечание « содержится в Полилог пространстве» является намного слабее , чем гипотеза . $EXP = PSPACE$ $P$ $P$ $NC = P$

Более подробно: Поскольку семейства цепей имеют глубину для некоторой константы, каждое такое семейство цепей может быть оценено в пространстве . Следовательно, . Таким образом, подразумевает . Применение перевода (замена на ) подразумевает . Существование полного языка в завершает аргумент. $NC$ $(\log n)^c$ $O((\log n)^c)$ $NC \subseteq \bigcup_{c > 0} SPACE[(\log n)^c]$ $P = NC$ $P \subseteq \bigcup_{c > 0} SPACE[(\log n)^c]$ $n$ $2^n$ $TIME[2^{O(n)}] \subseteq PSPACE$ $EXP$ $TIME[2^{O(n)}]$

Обновление: отвечая на дополнительный вопрос Андреаса, я полагаю, что можно доказать что-то вроде: если для всех каждый полиномиально разреженный язык в разрешим в пространстве полилога. (Быть полиномиально разреженным означает, что в языке имеется не более строк длины для всех .) Если это правда, доказательство, вероятно, будет идти в духе доказательства Хартманиса, Иммермана и Сьюэлсона, что тогда и только тогда каждый полиномиально редкий язык в содержится в . (Примечание, $EXP=PSPACE$ $c$ $n^{O(\log^c n)}$ $poly(n)$ $n$ $n$ $NE = E$ $NP$ $P$ $n^{O(\log^c n)}$ времени в пространстве полилога все еще достаточно, чтобы подразумевать .) $PSPACE=EXP$

Райан Уильямс
источник

Спасибо за хороший ответ. Теория вычислений Декстера Козена имеет красивую «унифицированную» запись для классов Руццо на странице 69: где ограничивает пространство, ограничивает время, а ограничивает чередования. Тогда а который действительно подчеркивает конструкцию.

S T A (f, g, h)

$STA(f,g,h)$

f

$f$

g

$g$

h

$h$

NC = S T A (\log n, *, (\log n)^{O (1)})

$\text{NC} = STA(\log n, {*}, (\log n)^{O(1)})$

P = S T A (\log n, *, *)

$\text{P} = STA(\log n, {*}, {*})$

Андрас Саламон

Обратите внимание, что я говорю выше. Однако я думаю, что это то же самое. Машина, которая занимает полиномиальное время и пространство но выполняет только чередования может быть превращена в другую машину чередования, которая принимает только время и пространство. (Другое направление очевидно.) Идея состоит в том, чтобы добавить больше чередований, чтобы каждая полисиомально-временная экзистенциальная фаза и универсальная фаза "ускорялись", чтобы работать только за время и пространство по теореме Савича.

N C = S T A (\log n, (\log n)^{O (1)}, *)

$NC = STA(\log n, (\log n)^{O(1)}, *)$

O (\log n)

$O(\log n)$

(\log n)^{O (1)}

$(\log n)^{O(1)}$

(\log n)^{O (1)}

$(\log n)^{O(1)}$

O (\log n)

$O(\log n)$

(\log n)^{O (1)}

$(\log n)^{O(1)}$

O (\log n)

$O(\log n)$

Райан Уильямс

нам нужен какой-то скрипт greasemonkey, который автоматически связывает что-то вроде «\ NP» со входом в зоопарк.

Суреш Венкат

(Я видел ответ Райана, но я просто хотел представить другую точку зрения, которая была слишком длинной, чтобы вписаться в комментарий.)

В доказательстве все, что вам нужно неофициально знать о L, это то, что когда его взрывают по экспоненте, L становится PSPACE. То же самое доказательство применимо и к NL, потому что NL, взорванное экспонентой, также становится PSPACE. $L = P \Rightarrow PSPACE = EXP$

Точно так же, когда NC взрывается по экспоненте, вы получаете PSPACE. Мне нравится видеть это с точки зрения схем: NC - это класс схем полиномиального размера с глубиной полилога. Когда взорван, это становится экспоненциальным размером контуров с полиномиальной глубиной. Можно показать, что это в точности PSPACE, как только будут добавлены соответствующие условия однородности. Я думаю, если NC определен с L-однородностью, то это получит PSPACE-равномерность.

Доказательство должно быть легким. В одном направлении возьмите задачу, полную PSPACE, такую как TQBF, и выразите квантификаторы, используя вентили AND и OR экспоненциального размера. В другом направлении попробуйте рекурсивно пересечь контур глубины полинома. Размер стека будет полиномиальным, поэтому это можно сделать в PSPACE.

Наконец, я пришел к этому аргументу, когда увидел вопрос (и до прочтения ответа Райана), поэтому могут быть ошибки. Пожалуйста, укажите их.

Робин Котари
источник

Одно исправление: NC имеет схемы полиномиального размера и глубины полилога, но это все еще только полиномиальная глубина после перевода.

Райан Уильямс

@ Райан: Ты прав. Я исправлю это.

Робин Котари

Вот еще немного подробнее с точки зрения моделирования пространственно-временной ограниченной Чередующейся машины Тьюринга.

Предположим, что . $P = NC$

Поскольку , мы получаем $NC = ATISP((\log(n))^{O(1)}, O(\log(n)))$

P = A T I S P ((\log (n))^{O (1)}, O (\log (n))) .

$P = ATISP((\log(n))^{O(1)}, O(\log(n))).$

Теперь рассмотрим задачу линейного универсального моделирования которой нам дано кодирование на машине Тьюринга и входная строка длины и мы хотим знать, принимает ли не более чем за шагов. $LinU$ $M$ $x$ $n$ $M$ $x$ $n$

Мы знаем , что . Следовательно, существует постоянная (достаточно большая) такая, что $LinU \in P$ $c$

(*) L i n U \in A T I S P (\log^{c} (n), c \log (n)) .

$(*) \; LinU \in ATISP(\log^c(n), c\log(n)).$

В результате аргумента заполнения (немного хитрого, смотрите комментарии), мы имеем

(1) D T I M E (n) \subseteq A T I S P (\log^{c} (n), c \log (n)) .

$(1) \; DTIME(n) \subseteq ATISP(\log^c(n), c\log(n)).$

Расширяя аргумент заполнения, мы получаем

(2) D T I M E (n^{k}) \subseteq A T I S P (k^{c} \log^{c} (n), k c \log (n)) .

$(2) \; DTIME(n^k) \subseteq ATISP(k^c\log^c(n), kc\log(n)).$

(3) D T I M E (2^{n^{k}}) \subseteq A T I S P (k^{c} n^{k c}, k c n^{k}) .

$(3) \; DTIME(2^{n^k}) \subseteq ATISP(k^cn^{kc}, kcn^{k}).$

Кроме того, существуют известные результаты моделирования чередующихся пространственно-временных машин Тьюринга. В частности, мы знаем, что

A T I S P (\log^{c} (n), c \log (n)) \subseteq D S P A C E (O (\log^{c + 1} (n))) .

$ATISP(\log^c(n), c\log(n)) \subseteq DSPACE(O(\log^{c+1}(n))).$

Следовательно, мы (по существу) имеем следующее для всех натуральных чисел : $k$

(2^{*}) D T I M E (n^{k}) \subseteq D S P A C E (k^{c + 1} \log^{c + 1} (n))

$(2^{*}) \; DTIME(n^k) \subseteq DSPACE(k^{c+1}\log^{c+1}(n))$

(3^{*}) D T I M E (2^{n^{k}}) \subseteq D S P A C E (n^{k (c + 1)}) .

$(3^{*}) \; DTIME(2^{n^k}) \subseteq DSPACE(n^{k(c+1)}).$

Из мы получили бы этот . $(3^{*})$ $EXP = PSPACE$

==================== После мысли ===================

Важно отметить, что подразумевает для некоторой константы . $P = NC$

A T I S P ((\log (n))^{O (1)}, O (\log (n))) = A T I S P (\log^{c} (n), O (\log (n)))

$ATISP((\log(n))^{O(1)}, O(\log(n))) = ATISP(\log^c(n), O(\log(n)))$

c

$c$

Любые комментарии или исправления приветствуются. :)

Майкл Вехар
источник

@MichaelWehar Знаем ли мы при любом фиксированном ? В частности, мы знаем и, следовательно, ?

N C^{k} ⊊ P S P A C E

$NC^k\subsetneq PSPACE$

k

$k$

N C^{2} ⊊ P S P A C E

$NC^2\subsetneq PSPACE$

N C \neq P S P A C E

$NC\neq PSPACE$

T ....

@MichaelWehar Я не знаю, но я никогда не видел, чтобы . Фактически, комментарий в cstheory.stackexchange.com/questions/39046/… говорит, что возможно. Я разместил уточняющий запрос в cstheory.stackexchange.com/questions/40689/… . Как вы думаете, вы можете посмотреть?

N C \neq P S P A C E

$NC\neq PSPACE$

P - u n i f o r m N C^{1} = P S P A C E

$P-uniform NC^1=PSPACE$

T ....

@ Турбо Большое спасибо за добрый ответ !! Это может зависеть от вида униформы. Например, может выполняться только для логически-однородного ЧПУ. Позвольте мне подумать об этом и вернуться к вам. :)

N C = A T I S P ((\log (n))^{O (1)}, O (\log (n)))

$NC = ATISP((\log(n))^{O(1)}, O(\log(n)))$

Майкл Вехар

@ Турбо Спасибо за продолжение !! Я действительно думаю, что вы должны прочитать определение внизу страницы 370 от: sciencedirect.com/science/article/pii/0022000081900386

Майкл Вехар

@ Турбо Спасибо за все ваши наблюдения! Я настоятельно рекомендую вам прочитать статью, которую я связал, потому что в ней говорится, что большинство этих понятий однородного эквивалентны. Однако в статье не рассматривается -однородная которая может отличаться, поскольку у меня нет возможности доказать, что она одинакова.

N C

$NC$

P

$P$

N C

$NC$

Майкл Вехар