Размер арифметических схем является одним из наиболее естественных мер сложности полиномов. Так как арифметические схемы обобщают булевы схемы, доказывать для них нижние оценки должно быть проще, поэтому доказательство суперполиномиальной нижней оценки на размер арифметических схем для явно заданного полинома будет очень неплохим
разогревом перед доказательством "NC_1 не содержит P". К сожалению, несмотря на многолетние изучение, прогресс в этом направление не внушает оптимизма.
Чтобы еще немного упростить вопрос, можно рассмотреть модель некоммутативных арифметических схем. Это звучит как очень хорошая идея, так как некоммутативные арифметические схемы является прямым обобщением обычных арифметических схем. К тому же для некоммутативных арифметических формул мы знаем экспоненциальные нижние оценки. Однако
для схем не удалось получить никаких новых результатов. В докладе будет предложено объяснение, почему доказать суперлинейную нижнюю оценку может оказаться сложнее чем казалось изначально. А именно: такая оценка может быть амплифицированна до суперполиномиальной.