100
правок
Изменения
Нет описания правки
<tex>\oplus \notin \mathrm{AC^0}</tex>.
|proof=
Рассмотрим произвольную схему из [[Классы NC и AC| класса]] <tex>\mathrm{AC^0}</tex>. Не умаляя общности, будем считать, что:
# Выходная степень каждого элемента равна <tex>1</tex>.
# Схема имеет <tex>2n</tex> входных провода, причем последние <tex>n</tex> из них являются отрицанием первых <tex>n</tex> входов.
