Разрушается ли иерархия

Знаем ли мы, что иерархия не разрушается ( для всех )? $\mathsf{TC^0}$ $\mathsf{TC^0_d} \subsetneq \mathsf{TC^0_{d+1}}$ $d$

В записи Zoo для $\mathsf{TC^0}$ упоминается только расстояние между глубиной 2 и 3.

Кроме того, есть стандартная ссылка на тот факт , что иерархия не разрушается? $\mathsf{AC^0_d}$

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

С этим связан вопрос: сколько различных функций существует в

? Разумная нижняя граница для этих величин ответит на ваши вопросы. Также доказательство тесноты леммы о переключении Хастада, возможно, ответит на ваш второй вопрос.

A C_{d}^{0}

$AC_d^0$

T C_{d}^{0}

$TC_d^0$

MCH

Что касается второго вопроса, я полагаю, что он был впервые доказан в статье Сипсера STOC '83 "Борелевские множества и сложность схем" . Это дает только суперполиномиальные нижние границы. Первые экспоненциальные нижние оценки были даны Яо, а затем улучшены Хостадом.

Робин Котари

@ MCH, ты хотел написать

? Или вы имеете в виду число классов эквивалентности задач в

относительно

сокращений?

T C_{d}^{0} / A C_{d}^{0}

$\mathsf{TC^0_d}/\mathsf{AC^0_d}$

T C_{d}^{0}

$\mathsf{TC^0_d}$

A C_{d}^{0}

$\mathsf{AC^0_d}$

Каве

То, что я имею в виду, очень просто: сколько различных функций может представлять класс цепей

размера

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

, все готово.

A C_{d}^{0}

$AC_d^0$

s

$s$

d

$d$

MCH

@Dilworth, неоднородный. Кажется, что подсчет не работает, в противном случае, как я отметил ниже, мы могли бы затем отделить

от

который является открытым.

T C^{0}

$\mathsf{TC^0}$

N C^{1}

$\mathsf{NC^1}$

Каве

Ответы:

Мы не знаем хороших нижних границ (то есть, скажем, суперполиномиальной нижней границы для языка в ) для пороговых контуров глубины 2 (неограниченные веса). Контуры глубины 3, построенные из мажорных ворот, то есть содержат этот класс, и поэтому мы также не знаем хороших нижних границ для этого класса. $\mathsf{NEXP}$ $\mathsf{TC}^0_3$

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

Это отвечает на мой вопрос. Спасибо, Кристоффер.

Каве

_{2}^{0}

$^0_2$

^{0}

$^0$

_{2}^{0}

$_2^0$

@ Дилворт, я думаю, это потому, что он определяется с использованием большинства, а не порога.

Каве

Хм .. что ты имеешь в виду именно? Связано ли это с запиской Кристоффера о «неограниченных весах»?

Дилворт

$\mathsf{TC^0_d}$ $\mathsf{NC^1}$ $\mathsf{TC^0}$

$BFE$ $BFE$ $\mathsf{NC^1}$ $\mathsf{AC^0}$

$BFE$ $\mathsf{NC^1}$ $\mathsf{AC^0_2}$

$\mathsf{NC^1}=\mathsf{TC^0}$ $BFE \in \mathsf{TC^0_d}$ $d$ $\mathsf{NC^1} \subseteq \mathsf{TC^0_{d+2}}$ $\mathsf{TC^0} \subseteq \mathsf{TC^0_{d+2}}$

$d$

$\mathsf{TC^0} \not\subseteq \mathsf{TC^0_d}$ $\mathsf{NC^1} \not\subseteq \mathsf{TC^0_{d+2}}$ $BFE \notin \mathsf{TC^0_d}$

Кава
источник