Мой вопрос заключается в том, почему нижние оценки для логических схем глубины 3 с логическими элементами "и" и "xor" для определителя не подразумевают такие же нижние оценки для арифметических схем над ?
Что не так со следующим аргументом: Пусть - определитель, вычисляющий арифметическую схему, тогда, взяв все переменные mod 2, мы получим определитель, вычисляющий логическую схему.
Для арифметических схем над ваш аргумент совершенно прав. Тот же аргумент работает для арифметических схем над которые не используют дробей где четно.Q a / b b
Однако аргумент больше не работает, если вы говорите об арифметических схемах над другими кольцами, таких как: общие арифметические схемы над (т.е. без ограничения выше), , поля алгебраических чисел, или конечные поля с .R C F q q ≠ 2
(По сути, это та же самая причина, по которой в алгебраической геометрии часто рассматривается как так называемая «смешанная характеристика», а не нулевая характеристика.)
Однако булевы нижние оценки глубины 3 для цепей с {AND, OR, NOT} менее легко связаны с нижними оценками для арифметических схем над . (Да, {AND, XOR} - это полная основа, но, как правило, каналы глубины 3 по {AND, OR, NOT}, которые вы считаете воротами NOT свободными, в то время как при реализации NOT с XOR вы затем используете вентиль XOR, который вы фактически считаете Точно так же, хотя , когда вы реализуете этот единственный вентиль OR с AND и XOR, вы получаете небольшой гаджет глубины 3.) a ∨ b = ¬ ( ¬ a ∧ ¬ b )
Общее утверждение таково: пусть - многочлен с коэффициентами в кольце , и пусть - гомоморфизм кольца. Применяя к каждому коэффициенту вы получаете многочлен с коэффициентами в , который я . Затем нижняя граница для вычисления от -арифметических цепей означает то же нижняя граница для вычисления от -арифметических цепей.R φ : R → S φ f S f S f S S f R