Некоторые вопросы по параллельным вычислениям и классу NC

У меня есть ряд связанных вопросов по этим двум темам.

Во- первых, большинство текстов сложности только замазывать класс $\mathbb{NC}$ . Есть ли хороший ресурс, который более подробно освещает исследования? Например, то, что обсуждает все мои вопросы ниже. Кроме того, я предполагаю, что $\mathbb{NC}$ все еще видит значительный объем исследований из-за его связи с распараллеливанием, но я могу ошибаться. Раздел в зоопарке сложности не очень помогает.

Во-вторых, вычисление над полугруппой происходит в $\mathbb{NC}^1$ если мы предположим, что операция полугруппы занимает постоянное время. Но что, если операция не требует постоянного времени, как в случае неограниченных целых чисел? Существует ли какая - либо известные $\mathbb{NC}^i$ -полных проблема?

В-третьих, поскольку $\mathbb{L} \subseteq \mathbb{NC}^2$ , существует ли алгоритм для преобразования любого алгоритма пространства журнала в параллельную версию?

В- четвертых, это звучит , как и большинство людей считают , что $\mathbb{NC} \ne \mathbb{P}$ таким же образом , что $\mathbb{P} \ne \mathbb{NP}$ . Какова интуиция за этим?

В-пятых, каждый текст, который я прочитал, упоминает класс но не дает примеров проблем, которые он содержит. Есть ли?$\mathbb{RNC}$

Наконец, в этом ответе упоминаются проблемы в с сублинейным параллельным временем выполнения. Каковы некоторые примеры этих проблем? Существуют ли другие классы сложности, которые содержат параллельные алгоритмы, о которых не известно, что они находятся в N C ?$\mathbb{P}$$\mathbb{NC}$

В-третьих, поскольку , существует ли алгоритм для преобразования любого алгоритма пространства журнала в параллельную версию?$\sf{L} \subseteq \sf{NC}^2$

Можно показать (учебник Ароры и Барака), учитывая -время TM M , что забывающий TM M ′ (то есть TM, чье движение головы не зависит от его входа x ) может построить схему C n для вычисления M ( х ) где | х | = п .$t(n)$$M$$M'$$x$$C_n$$M(x)$$|x| = n$

Эскиз доказательства в соответствии с тем, что моделирует M и определяет «снимки» его состояния (то есть положения головы, символы на головках) на каждом временном шаге t i (представьте себе журнал вычислений). Каждый шаг t i можно вычислить из x и состояния t i - 1 . Поскольку каждый снимок включает только строку постоянного размера, и существует только постоянное количество строк этого размера, снимок в момент времени t i может быть вычислен схемой постоянного размера.$M'$$M$$t_i$$t_i$$x$$t_{i-1}$$t_i$

Если вы составляете схемы постоянного размера для каждого у нас есть схема, которая вычисляет M ( x ) . Используя этот факт, наряду с ограничением того, что язык M находится в L, мы видим, что наша схема C n по определению является лог-пространственно-равномерной , где единообразие просто означает, что наши схемы в нашем семействе схем { C n } вычисляют M ( x ) у всех одинаковый алгоритм. Не индивидуальный алгоритм для каждой схемы, работающей на входном размере n .$t_i$$M(x)$$M$$\sf{L}$$C_n$$\{C_n\}$$M(x)$$n$

Опять же, из определения равномерности мы видим, что схемы, определяющие любой язык в должны иметь функцию размера ( n ), вычисляемую в O ( log n ) . Семейство цепей A C 1 имеет не более O ( log n ) глубины.$\sf{L}$$\text{size}(n)$$O(\log n).$$\sf{AC}^1$$O(\log n)$

Наконец, можно показать, что дает соотношение, о котором идет речь.$\sf{AC}^1 \subseteq \sf{NC}^2$

В- четвертых, это звучит , как и большинство людей считают , что таким же образом , что P ≠ N P . Какова интуиция за этим?$\sf{NC} \neq \sf{P}$$\sf{P} \neq \sf{NP}$

Прежде чем идти дальше, давайте определим, что означает -полнота.$\sf{P}$

Язык является P -полным, если L ∈ P и каждый язык в P сводится к нему в лог-пространстве. Кроме того, если L является P -завершенным, то верно следующее$L$$\sf{P}$$L \in \sf{P}$$\sf{P}$$L$$\sf{P}$

1. $L \in \sf{NC} \iff \sf{P} = \sf{NC}$

2. $L \in \sf{L} \iff \sf{P} = \sf{L}$

Теперь мы рассматриваем как класс языков, эффективно определяемых параллельным компьютером (нашей схемой). В P есть некоторые проблемы, которые, по-видимому, противостоят любым попыткам распараллеливания (например, линейное программирование и проблема значений схемы). То есть некоторые проблемы требуют, чтобы вычисления выполнялись поэтапно.$\sf{NC}$$\sf{P}$

Например, проблема значения схемы определяется как:

Для данной схемы , входа x и вентиля g ∈ C , каков выход g на C ( x ) ?$C$$x$$g \in C$$g$$C(x)$

Мы не знаем, как вычислить это лучше, чем вычислять все ворота которые предшествуют g . Учитывая, что некоторые из них могут быть вычислены параллельно, например, если они все происходят на некотором временном шаге t i , но мы не знаем, как вычислить выходные данные затворов на временном шаге t i и временном шаге t i + 1 для очевидной трудности что ворота в t i + 1 требуют вывода ворот в t i !$g'$$g$$t_i$$t_i$$t_{i+1}$$t_{i+1}$$t_i$

Это интуиция за .$\sf{NC} \neq \sf{P}$

Пределы параллельных вычислений - это книга о полноте в том же духе, что и книга Garey & Johnson's N P- Complete.$\sf{P}$$\sf{NP}$

В-пятых, каждый прочитанный текст упоминает класс RNC, но не содержит примеров проблем, которые он содержит. Есть ли?

В работе «Сопоставление так же просто, как и в матричной инверсии» Мулмулей, Вазирани и Вазирани есть несколько примеров проблем в классе . Главное - найти максимальное совпадение, тогда они сводят другие проблемы к этому.$\mathbb{RNC}^2$