Четность

является класс схем полиномиального размера постоянной глубины с не воротами и неограниченным вентилятором-в И и ИЛИ воротах, где входы и ворота также имеют неограниченное разветвление.$AC^0$

Теперь рассмотрим новый класс, назовите его который похож на A C 0, но для которого входы и вентили имеют разветвление не более O ( 1 ) . Этот класс явно в A C 0 . На самом деле, он строго содержится в A C 0 , как отмечено здесь . Следовательно, PARITY явно не находится в A C 0 b f .$AC^0_{bf}$$AC^0$$O(1)$$AC^0$$AC^0$$AC^0_{bf}$

Есть ли доказательство PARITY которое также не проходит для A C 0 ? Другими словами, есть ли доказательства, в которых не используются такие мощные методы, как лемма о переключении или метод Разборова-Смоленского?$\notin AC^0_{bf}$$AC^0$

Я мог бы что-то пропустить, но разве совпадает с Формулой? Поскольку каждый входной бит может влиять не более чем на ограниченное число элементов, мы можем просто предположить, что каждый элемент имеет только один выход (после возможного дублирования нескольких вещей), и мы можем также отбрасывать не элементы. Мы знаем, что размер формулы четности равен n ^ 2 (см. Трой Дж. Ли, « Размер формулы PARITY », 2007), и поскольку на каждом уровне нашей схемы мы можем иметь только O (n) вентилей, это показывает, что четность не в A C 0 b f .$AC^0_{bf}$$AC^0_{bf}$

$S$$S^d$$S$$S$$AC^0$ $S^{1/d}$$AC^0$ $AC^0$$AC^0$$d$

$X$$1$$n$