i.1 Вычисление вещественных многочленов в полном арифметическом базисе A = {+,×,R} Для вычисления многочлена степени n достаточно: n аддитивных операций n/2+O(1) умножений (n 1/2 ) нескалярных операций Эти оценки неулучшаемы (Motzkin, Пан, Белага 1950-е гг. Paterson, Stockmeyer 1973)

i.2 Способ вычисления многочлена за n/2+O(log n) умножений (метод Винограда) Идея: пусть f(x) – нормированный многочлен степени 2 k+1 – 1 Тогда f(x) = (x 2 k + a) f 0 (x) + f 1 (x), (1) где f 0 (x), f 1 (x) – нормированные многочлены степени 2 k – 1 Разложение (1) применим к f 0 (x), f 1 (x) и т.д. Проверить: (а) необходимые степени x 2 k, x 2 k-1, …, x 2 вычисляются за k умножений (аддитивной цепочкой); (б) если они вычислены, то любой промежуточный многочлен степени 2 m – 1 вычисляется за 2 m-1 – 1 умножений (очевидно из (1))

i.3 Способ вычисления многочлена за 2n 1/2 нескалярных умножений Идея: многочлен f(x) степени rs – 1 представляется в виде f(x) = (…(( f 0 (x) x r + f 1 (x)) x r + … ) x r + f s-1 (x), (2) (схема Горнера) где f k (x) – многочлены степени r – 1 (а) степени x 2, x 3, …, x r вычисляются за r – 1 нескалярных умножений; многочлены f k (x) получаются как линейные комбинации этих степеней; (б) для завершения вычислений по формуле (2) достаточно выполнить еще s – 1 умножений на x r

i.4 Эффективные нижние оценки В х гг. Straßen и его ученики (von zur Gathen, Heintz, Schnorr, Stoß, Baur, Halupczok, а также Sieveking, van de Wiele) построили примеры конкретных многочленов, имеющих сложность, близкую к максимально возможной. Коэффициенты таких многочленов, как правило, алгебраически независимые вещественные или быстро растущие рациональные числа. Примеры сложных многочленов: Σ p i 1/2 x i Σ 2 2 i x i Σ i r x i Здесь: p i P, r Q / Z

i.5 Подстановка Кронекера x i = x 2 i устанавливает взаимно однозначное соответствие между многочленами одной переменной степени 2 n –1 и мультилинейными (линейными по каждой переменной) многочленами n переменных Поэтому если f(x) соответствует g(x 0, …, x n-1 ), то L(f) L(g) + n – 1

ii.1 Рассматриваются монотонные многочлены, т.е. с неотрицательными вещественными коэффициентами, и сложность их реализации над монотонным арифметическим базисом A + = {+,×,R + }. Содержательной является задача построения сложных многочленов с коэффициентами 0 и 1 ii.2 Субкспоненциальные нижние оценки Первая сверхполиномиальная нижняя оценка получена для характеристического многочлена наличия k-клики в графе: CL n,k = Σ Π x i s, i t 1 i 1 < … < i k n 1 s < t k L + (CL n,k ) C n k – 1, в частности, L + (CL n,n/2 ) 2 n-o(n) Schnorr 1976

Помимо Шнорра нижние оценки вида 2 Ω(n) для мультилинейных многочленов n переменных в начале 80-х гг. получали Valiant, Jerrum, Snir ii.3 Экспоненциальные нижние оценки 2 n/2 – 1 Касим-Заде 1983 Ω(2 2n/3 ) Гашков n-o(n) Гашков, Сергеев 2010 (далее подробно)

iii.1 ОПР. Подмножество M коммутативной полугруппы (G, +) называется (k, l)-редким, где kl, если для любых подмножеств A, B G, таких, что |A|=k и |B|=l выполнено A × B = { a+b | a ϵ A, b ϵ B } M При k=l используем термин k-редкое подмножество. Пример: Подмножество {0, 1, 3} (Z 7, +) является 2-редким ОПР. Пусть f – многочлен n переменных. Тогда mon f (N {0}) n – множество вектор-степеней его мономов.

iii.2 ОСНОВНАЯ ТЕОРЕМА Пусть k1 и mon f – (k, l)-редкое подмножество (N {0}) n, L + (f) – аддитивная монотонная сложность многочлена f, L × (f) – мультипликативная монотонная сложность f, α(k) – наибольшее число булевых векторов длины k – 1, ни один из которых не равен дизъюнкции нескольких других. Пусть h = min { (k – 1) 3, (l – 1) 2 }. Тогда: (i) L + (f) h -1 | mon f | – 1 (ii) L × (f) C k, l | mon f | α(k)/(2α(k)-1) – n – 2 В частности, L × (f) = Ω(| mon f | 2/3 ) при k=l=2 и L × (f) = Ω(| mon f | 3/5 ) при k=l=3. Эти оценки по порядку неулучшаемы Гашков 1987

iii.3 Примеры 2- и 3-редких множеств большой мощности 1. 2-редкие подмножества Z n мощности ~n 1/2 : Множество В.Е. Алексеева 1979: Пусть n=p(p–1), pP, ζ – порождающий элемент мультипликативной группы поля Z p. Тогда M = { s i | i= 0, …, p-2 }, где s i i mod (p-1), s i ζ i mod p Множество Зингера 1938: Пусть n=q 2 +q+1, q – степень простого числа, θ – примитивный элемент поля GF(q 3 ). Пусть GF(q) = { ζ 1, …, ζ q }. Тогда M = {0} { s i | θ s i / (θ + ζ i ) GF(q), i=1, …, q }

ОПР. E m = { 0, …, m-1 } редкие подмножества E m n мощности ~m n/2 : Пусть q = p k, pP\{2}. Тогда M = { (x, x 2 ) | x GF(q) } GF(q 2 ) E p 2k Пусть q = 2 k. Тогда M = { (x, x 3 ) | x GF(q) } GF(q 2 ) E 2 2k 3. 3-редкие подмножества E m n мощности ~m 2n/3 : Множество Брауна 1966: Пусть q = p k, pP\{2} и γ – квадратичный невычет в GF(q). Тогда M = { (x, y, z) | x 2 + y 2 + z 2 = –γ, x, y, z GF(q) } GF(q 3 ) E p 3k

iii.4 Следствия для сложности многочленов Можно эффективно указать многочлен f от n переменных степени не выше m – 1 по каждой переменной, такой, что (при определенных ограничениях на m и n) L + (f) (1 – o(1))m n/2 L × (f) (2 – o(1))m n/3 (если в качестве mon f выбирается подходящее 2-редкое множество) или L + (f) (1/8 – o(1))m 2n/3 L × (f) (2 -4/5 – o(1))m 2n/5 (если в качестве mon f выбирается подходящее 3-редкое множество) (в примерах Шнорра и Касим-Заде: 2-редкие множества)

Факт (Erdös, Spencer 1974): любое (k, l)-редкое подмножество M E m n имеет мощность O k, l (m n(1-1/k) ) iii.5 Редкие множества экстремальной мощности Множество Коллара-Роньяи-Жабо 1996: В группе (GF(q t ), +) множество элементов единичной нормы M = { x | x (q t -1)/(q-1) = 1, x GF(q t ) } является (t, t!+1)-редким подмножеством и имеет мощность (q t – 1)/(q – 1).

iii.6 ЛЕММА 1 Пусть ψ s, t, m : E m st E s (2m-1) t – взаимно однозначное отображение: ψ s, t, m ( …, a it, …, a it+t-1, … ) = ( …, [ a it, …, a it+t-1 ] 2m-1, … ) * Тогда если M E m st является (k, l)-редким подмножеством, то ψ s, t, m (M) E s (2m-1) t также является (k, l)-редким подмножеством. * [ a k, …, a 0 ] m = (…(a k m + a k-1 )m + … )m + a 0 (запись числа в системе счисления с основанием m)

iii.7 ОСНОВНОЕ СЛЕДСТВИЕ (из основной теоремы и технической теоремы 1) Пусть m 2 и n 1. Можно эффективно указать многочлен f от n переменных степени не выше m – 1 по каждой переменной, такой, что при m n L + (f) m n (1 - o(1)) L × (f) m n (1/2 - o(1)) Обе оценки в таком виде уже неулучшаемы.

iv.1 Примеры расхождения между сложностью L(f) в полном базисе A = {+,×,R} и сложностью L M (f) в монотонном базисе A + = {+,×,R + } f – мультилинейные многочлены n переменных: L(f) = n O(1) L M (f) c n 1/2 Valiant 1979 L(f) = n O(1) L M (f) c n Касим-Заде 1983 L M (f) / L(f) = n Ω(1) deg f = 3 Schnorr 1976 L M (f) / L(f) 2 n(1/2-o(1)) Гашков, Сергеев 2010 L M (f) / L(f) = n 1-o(1) deg f = 2 Гашков, Сергеев 2010

iv.2 Еще один способ построения редких множеств ОПР. Булева матрица называется (k, l)-редкой, если она не содержит подматриц размера k × l, состоящих из всех единиц ЛЕММА 2 Пусть M 1 = { a 1, …, a r } и M 2 = { b 1, …, b r } – k-редкие подмножества E m n и (μ i, j ) – l-редкая матрица порядка r. Тогда (i) M = { ( a i, b j ) | μ i, j = 1 } E m 2n (ii) M = { a i + (2m – 1) b j | μ i, j = 1 } E n m 2 – ((k – 1)(l – 1)+1)-редкие подмножества Свойство: L(f M ) L( f a 1, …, f a r, f b 1, …, f b r ) + L(μ i, j ) + O(log m), где M = mon f M, L(μ i, j ) – сложность линейного преобразования

СЛЕДСТВИЕ (из леммы 1 и результата Kόllar, Rόnyai, Szabό) Можно явно указать n o(1) -редкую циркулянтную матрицу порядка n и веса n 2-o(1) СЛЕДСТВИЕ (из леммы 2) Пусть f – многочлен с коэффициентами 0 и 1, такой, что M = mon f. Пусть (μ i, j ) – r o(1) -редкая циркулянтная матрица и пусть k = r o(1) и либо n log m = r o(1), либо deg f = r o(1). Тогда L M (f)=Ω(r 2-o(1) ) L(f) r 1+o(1)

iv.3 СЛЕДСТВИЕ (о расхождении между монотонной и немонотонной сложностью) Пусть m 2 и n 1. Можно эффективно указать многочлен f от n переменных степени не выше m – 1 по каждой переменной, такой, что при m n L M (f) / L(f) m n (1/2 - o(1)) iv.4 Пример многочлена степени 2 Пусть (μ i, j ) – n o(1) -редкая циркулянтная матрица порядка n и веса n 2-o(1). Определим f = Σ μ i, j x i y j 1 i < j n Тогда L M (f) / L(f) = n 1-o(1)