Теоремы об иерархии для глубины контура

11

Какие теоремы иерархии существуют для глубины контура?

Заявления как

если и то . $g(n) \in o(f(n))$ $f(n) \in n^{O(1)}$ $\mathsf{SizeDepth}(n^{O(1)}, g(n)) \subsetneq \mathsf{SizeDepth}(n^{O(1)}, f(n))$

cc.complexity-theory circuit-complexity hierarchy-theorems circuit-depth Кава
источник

3

Не важно. Мы не знаем, если

{N C}^{1} = P / p o l y

$\mathsf{NC}^1 = \mathsf{P}/\mathrm{poly}$ !

Кристоффер Арнсфельт Хансен

@Kristoffer, да, это верно, я привел это как пример того типа заявлений, которые я ищу. Другими словами, интересные классы схем, где увеличение глубины, как известно, увеличивает класс.

Каве

2

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

f

$f$ равна

\approx

$\approx$ логарифму минимального размера формулы для

f

$f$ . Теперь иерархия для размера формулы должна отображаться так же, как для размера схемы (с использованием результатов Шеннона-Лупанова). Скажем, цепи размера

4 t

$4t$ , сильнее, чем цепи размера

t

$t$ . Конечно, все становится немного сложнее, если мы требуем, чтобы размер был полиномиальным.

Стасис

8

В статье Клаве, Пола, Пиппенгера и Яннакакиса приведена теорема об иерархии для монотонных формул постоянной глубины: http://dl.acm.org/citation.cfm?id=808717

В частности, для каждого он дает функцию, которая может быть вычислена по формуле глубины и размера но требует формулы глубины размера . $k$ $k$ $n$ $k-1$ $\exp(n^{1/k})$

Или меир
источник

7

Раз и Маккензи в разделе «Разделение монотонной иерархии NC» показывают, что монотонная иерархия NC является строгой, и отделяют монотонную NC от монотонной P.

Юваль Фильмус
источник

Теоремы об иерархии для глубины контура

Ответы: