Техники уменьшения глубины схем

Наилучшей нижней оценкой для схем без ограничений на глубину, базис и исходящую степень на протяжении нескольких десятилетий оставалась оценка 3n. Более того, метод элиминации элементов, которым была доказана эта и многие предыдущие оценки, в текущем виде не способен дать оценок сильнее $5n$. В данной работе мы представим способ доказательства нижних оценок, основанный не на элиминации элементов. Мы покажем, что любую схему размера s можно переписать как дизъюнкцию $2^{s/3.9} 16-КНФ$. Несмотря на то, что этот структурный результат не даёт немедленно новые нижние оценки, он даёт новый потенциальный способ.
Наш результат дополняет классический результат Вэлиэнта 70-х годов, который говорит, что любую схему линейного размера и логарифмической глубины можно переписать как дизъюнкцию$ 2^{an} n^b-КНФ$ (где a, b — константы). Известно, что такой графовый подход не даёт нетривиальных оценок для схем суперлогарифмической глубины. Мы обходим это препятствие, рассматривая не только граф схемы, но и то, какие вычисления происходят внутри.