схема оценки

Известно , что если проблема оценки цепи в ? Как насчет (Uniform )? $\mathsf{NC^1}$ $\mathsf{NC^1}$ $\mathsf{ALogTime}$ $\mathsf{NC^1}$

Мы знаем, что схемы глубины могут быть оценены схемами глубины где - универсальная постоянная. Это означает, что схемы глубины могут быть оценены схемой глубины . Однако не содержит функции, которая в конечном итоге доминирует над всеми функциями в . $k$ $k+c$ $c$ $k\lg n + o(\lg n)$ $O(\lg n)$ $O(\lg n)$ $O(\lg n)$

Мы знаем, что проблема оценки формулы находится в . Каждая схема эквивалентна булевой формуле. Разве мы не можем вычислить расширенное представление соединения эквивалентной булевой формулы из заданной схемы в ? $\mathsf{ALogTime}$ $\mathsf{NC^1}$ $\mathsf{NC^1}$ $\mathsf{ALogTime}$

Расширенное представление соединения из схемы включает в себя

количество ворот в цепи,
тип каждой калитки и
для каждого вентиля и каждого пути в группе DAG схемы эти ворота достигли следующего по пути . $g$ $\pi$ $g$ $\pi$

Путь задается последовательностью 0/1, где 0 представляет перемещение к левому родителю, а 1 представляет перемещение к правому родителю. Обратите внимание, что количество путей является полиномиальным: длина путей ограничена глубиной контура.

cc.complexity-theory reference-request circuit-complexity Кава
источник

Насколько я знаю, оценка

не известна как

, и предполагается, что она находится за пределами

. См. «О теориях ограниченной арифметики для

», Е. Jerabek, Ann. Чистое приложение Логика 2011 ( math.cas.cz/~jerabek/papers/vnc.pdf ).

N C^{1}

$NC^1$

N C^{1}

$NC^1$

N C^{1}

$NC^1$

N C^{1}

$NC^1$

Иддо Цамерет

@IddoTzameret Может быть, вы должны сделать свой комментарий ответом.

Дай Ле

Что вы подразумеваете под оценкой NC1-цепи? Вы имеете в виду, что вход, данный для оценщика, является схемой

, глубина которой ограничена

для некоторой фиксированной константы

, где

- количество входов в

C

$C$

c \log (n)

$c\log(n)$

c

$c$

n

$n$

C

$C$

Игорь Шинкарь

@ Игорь, хорошая мысль. Я должен подумать и уточнить.

Каве

@igor, я думаю, мы можем предположить, что глубина контура составляет

для некоторой произвольной, но фиксированной константы

поскольку это трудно для

при сокращениях

c \lg n

$c \lg n$

c \geq 1

$c\geq 1$

N C^{1}

$\mathsf{NC^1}$

A C^{0}

$\mathsf{AC^0}$

Каве

Ответы:

Насколько я знаю, оценка не известна как , и предполагается, что она находится за пределами . Видеть $\mathsf{NC^1}$ $\mathsf{NC^1}$ $\mathsf{NC^1}$

Эмиль Джерабек, " О теориях ограниченной арифметики для $\mathsf{NC^1}$ ", Ann. Чистое приложение Логика 2011

Иддо Цамерет
источник

Спасибо, Иддо. Я смотрю на статью Эмиля, и это очень полезно. Он утверждает , что проблема не известна, что в

, если мы используем прямое представление соединения , но оно находится в

, если мы используем расширенное представление соединения .

N C^{1}

$\mathsf{NC^1}$

N C^{1}

$\mathsf{NC^1}$

Каве

Далее он утверждает, что следующая проблема является основной трудностью вычисления оценки

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

N C^{1}

$\mathsf{NC^1}$ $G$ $n$ $x,y \in G$ $d \leq \log n$ $y$ $x$ $d$

Каве

@Kaveh, вы также можете взглянуть на «Усиление нижних границ с помощью самовосстанавливаемости» Аллендера и Кокики (JACM 2010). Они также заявляют, что проблема оценки

не известна в

N C^{1}

$NC^1$

N C^{1}

$NC^1$

Иддо Цамерет

На самом деле эта линия была вдохновением для моего вопроса. Я чувствовал, что это должно быть в

если мы используем расширенное представление соединения и статья Эмиля утверждает, что это действительно так.

N C^{1}

$\mathsf{NC^1}$

Каве