Пусть обозначает минимальный размер (немонотонной) арифметической схемы, вычисляющей заданный полилинейный многочлен и обозначают минимальный размер (немонотонной) логической схемы, логическую версию для определяется как: ( + , × , - ) е ( х 1 , ... , х п ) = Σ е ∈ Е с й п Π я = 1 х е я яB ( f ) ( ∨ , ∧ , ¬ )
Известны ли полиномы для которых меньше, чем ? B ( f ) A ( f )
Если мы рассмотрим монотонные версии схем - без минус и без Not вентилей - тогда может быть даже экспоненциально меньше, чем : возьмем, например, полином с кратчайшим st-путем на ; тогда и . Но что происходит в «немонотонном мире»? Конечно, большие промежутки не могут быть известны только потому, что у нас нет больших нижних оценок на . Но, может быть, есть хоть какие-то небольшие пробелы? ( ¬ ) B ( f )
ПРИМЕЧАНИЕ (15.03.2016) В моем вопросе я не указал, насколько большие коэффициенты . Игорь Сергеев вспомнил, что, например, следующий (одномерный) многочлен имеет (Штрассен и люди его группы). Но для этого многочлена, так как . Мы можем получить Фрон в многомерный полином из переменных с помощью использования подстановки Кронекера. Свяжите с каждым показателем моном , гдеявляются 0-1 коэффициентами двоичного представления . Тогда желаемый многочлен имеет вид , и мы имеем, что Но логическая версия - это просто ИЛИ переменных, поэтому , и у нас есть четный экспоненциальный пробел. Таким образом, если величина коэффициентов может быть тройной экспоненциальной по числу переменных, то можно показать, что разрыв является даже экспоненциальным. (На самом деле, не сама величина - больше алгебраическая зависимость коэффициентов.) Вот почему реальная проблема с - это случай малых