Что такое большая версия NC?

$\mathsf{NC}$ отражает идею эффективного распараллеливания, и одна из его интерпретаций - это проблемы, которые разрешимы во времени с использованием параллельных процессоров для некоторых констант , . У меня вопрос, есть ли аналогичный класс сложности, где время равно а число процессоров - . Как заполнить пустой вопрос: $O(\log^c n)$ $O(n^k)$ $c$ $k$ $n^c$ $2^{n^k}$

$\mathsf{NC}$ для как _ _ для $\mathsf{P}$ $\mathsf{EXP}$

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

Каждый компьютер читает полиномиальное количество сообщений полиномиального размера, полученных им на предыдущем временном шаге.
На каждом компьютере выполняется какое-то многопоточное вычисление, которое может зависеть от этих сообщений.
Каждый компьютер передает сообщение (разной длины) каждому из своих соседей.

Как называется класс сложности, соответствующий этим моделям? Что такое хорошее место, чтобы прочитать о таких классах сложности? Есть ли полные проблемы для такого класса?

cc.complexity-theory reference-request complexity-classes circuit-complexity dc.parallel-comp Артем Казнатчеев
источник

связанный вопрос, я думаю: cstheory.stackexchange.com/q/2788/1037

Артем Казнатчеев

У нас есть , , , . Таким образом, соответствующий класс для может быть чем-то вроде и тогда соответствующий класс для будет . Это просто некоторая алгебраическая манипуляция, я не проверял, удовлетворяет ли она вашим требованиям, но я думаю, что она будет удовлетворять трем условиям, но не будет иметь экспоненциально много компьютеров. Я думаю, что вы должны отказаться от этого требования в противном случае (больше)

N C^{k} = A S p a c e T i m e (O (\log n), (\log n)^{k})

$NC^k = ASpaceTime(O(\log n), (\log n)^k)$

N C = A S p a c e T i m e (O (\log n), (\log n)^{O (1)})

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

P = T i m e (n^{O (1)})

$P = Time(n^{O(1)})$

E X P = T i m e (2^{n^{O (1)}})

$EXP = Time(2^{n^{O(1)}})$

N C^{k}

$NC^k$

A S p a c e T i m e (n^{O (1)}, 2^{O (\log n)^{k}})

$ASpaceTime(n^{O(1)}, 2^{O(\log n)^k})$

N C

$NC$

A S p a c e T i m e (n^{O (1)}, 2^{(\log n)^{O (1)}})

$ASpaceTime(n^{O(1)}, 2^{(\log n)^{O(1)}})$

Каве

полученный класс будет содержать и аналогия не будет держать в .

E X P

$EXP$

N C \subseteq P

$NC \subseteq P$

Каве

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

l o g n

$log n$

N C

$NC$

N C

$NC$

P T / W K (l o g^{c} n, n^{k}) / p o l y

$PT/WK(log^c n,n^k)/poly$

P T / W K (n^{c}, 2^{n^{k}}) / p o l y

$PT/WK(n^c ,2^{n^k})/poly$

Артем Казнатчеев

Это стандартно (хотя и не в зоопарке сложности), проверьте, например, Руццо, «О равномерной сложности схем», 1981. Также я думаю, что вы должны работать с однородными классами, каждая функция имеет экспоненциальное изменение размера / логическую глубину 2 схемы (и это будет удовлетворять трем условиям, если мы будем использовать ограниченный веер и глубину ). И, как я сказал, если экспоненциально много узлов, то аналогия не справедлива. Также основным свойством параллельных вычислений является экономия времени, например, в случае это логарифмическое время . Я думаю, что квазиполиномиальное время будет соответствовать полихороговому времени.

\log n

$\log n$

N C

$NC$

Каве

Ответы:

Я считаю, что класс, который вы ищете, это . Предположим, у вас есть процессоры , соответствующие требованиям: $PSPACE$ $exp(n^k) = 2^{O(n^k)}$

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

На каждом компьютере выполняется какое-то многопоточное вычисление, которое может зависеть от этих сообщений.

Каждый компьютер передает сообщение (разной длины) каждому из своих соседей.

Это можно смоделировать, имея схему с слоями, где у каждого слоя есть «ворота» , а каждый «гейт» выполняет вычисление за полиномиальное время (удовлетворяющее части 2) с полиномиальным разветвлением ( удовлетворяющий части 1), и имеет полиномиальное разветвление (удовлетворяющее части 3). $poly(n)$ $exp(n^k)$

Поскольку каждый элемент вычисляет полиномиальную функцию времени, каждый из них может быть заменен схемой полиномиального размера (с AND / OR / NOT) обычным способом. Обратите внимание, что полиномиальные разветвления и разветвления можно сделать равными 2, только увеличив глубину на коэффициент . То, что остается, является однородной схемой глубины с воротами И / ИЛИ / НЕ. Это точно чередующееся полиномиальное время, которое в точности соответствует . $O(\log n)$ $poly(n)$ $exp(n^k)$ $PSPACE$

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

Райан, я не понимаю, как вы размещаете экспоненциальное число компьютеров в полиномиально многих слоях, мне кажется, что глубина может быть экспоненциальной, не могли бы вы объяснить это немного подробнее, почему это возможно? Также мне кажется, что тривиальное построение схемы CNF произвольной заданной функции в виде схемы веер-2 будет удовлетворять требованиям, я что-то упустил?

Каве

@Kaveh: я не понимаю твой первый вопрос. Во-вторых, хотя для любой функции существует схема глубины 2 экспоненциального размера, NC (поли) требует, чтобы вы были в состоянии генерировать схемы равномерно, поэтому вы не можете создавать произвольные схемы для каждого входного размера.

Робин Котари

@ Робин, спасибо. Вероятно, я путаю вещи. (Я чувствую, что глубина контуров, соответствующих PSpace, должна быть экспоненциальной, также я думаю, что PSpace - это EXP, поскольку L - это P, поэтому говорить о том же, когда L заменяется на NC, странно для меня, я чувствую, что класс забота должна быть между PSpace и EXP.) Я должен подумать немного больше, чтобы понять, что здесь происходит.

Каве

@Kaveh, я назначил количество слоев (т. Е. Глубину) экспоненциальным, поэтому глубина по определению не может быть экспоненциальной. Процессоров экспоненциально много, поэтому вашему CNF понадобится экспоненциальная разветвленность, нарушающая одно из условий. Глубина схем экспоненциального размера, соответствующих PSPACE, является полиномиальной. Причина, по которой это верно, и причина, по которой обе аналогии являются «действительными» в некотором смысле («PSPACE означает EXP, так как L означает P», а «PSPACE означает EXP, как NC означает P»), потому что PSPACE = переменный полином Время. Мы не знаем, если L = переменное логарифмическое время (это NC1).

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

Думаю, я лучше понимаю ситуацию после прочтения ваших комментариев и комментариев Робина, спасибо.

Каве

Как говорит Райан, этот класс - PSPACE. Этот класс часто называют NC (поли) в литературе. Вот прямая цитата из статьи QIP = PSPACE :

Мы рассматриваем масштабированный вариант NC, который является классом сложности NC (poly), который состоит из всех функций, вычисляемых с помощью однородных семейств полиномиальных пространств булевых схем, имеющих полиномиальную глубину. (Обозначение NC (2 ^poly ) также ранее использовалось для этого класса [11].) Для решения задач известно, что NC (poly) = PSPACE [10].

[10] А. Бородин. Относительно времени и пространства к размеру и глубине. Журнал SIAM по вычислительной технике, 6: 733–744, 1977.

[11] А. Бородин, С. Кук, Н. Пиппенгер. Параллельные вычисления для хорошо наделенных колец и ограниченных в пространстве вероятностных машин. Информация и контроль, 58: 113–136, 1983.

Один из способов убедиться в этом - доказать оба включения напрямую. Чтобы увидеть, что NC (poly) находится в PSPACE, обратите внимание, что мы можем рекурсивно вычислить вывод конечного элемента, и нам потребуется только стек размером, равным глубине схемы, которая является полиномиальной. Чтобы показать, что PSPACE находится в NC (poly), обратите внимание, что QBF, который является PSPACE-полным, может быть записан как полиномиальная схема глубины с экспоненциально большим количеством шлюзов обычным способом - существующий квантификатор является вентилем ИЛИ, полным квантификатором это ворота И Поскольку квантификаторов всего много, это схема глубины полинома.

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