С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 44
Текст из файла (страница 44)
[], []. Результаты Кронекера, Шинцеля и Цассенхауза изложены в [,разд. .].Проблема орбитединицы, то у него найдется по меньшей мере один корень a, длякоторого | a | > 1. Бланксби и Монтгомери показали, что по меньшеймере для одного корня выполняется неравенство|a| ¾ 1 +1.30n2 ln(6n)(C.)Из этого позднее было выведено, что если корни неприводимого унитарного полинома f (x) степени n c целочисленными коэффициентами не являются корнями из единицы, то для любого натуральногорешения m уравнения (C.) выполнено неравенствоm ¶ n + 60n2 ln(6n)(ln(n + 1) + ln| q(x) |),(C.)где | q(x) | обозначает длину вектора коэффициентов полинома q(x):если q(x) = ck x k + ...
+ c1 x + c0 , тоÆ| q(x) | = c2k + ... + c21 + c20 .Решения уравнения (C.) для различных корней a полинома f (x)совпадают. Доказанное может быть сформулировано следующим образом.Предложение C.. Пусть f (x) — неприводимый над Q полиномстепени n, корни которого не являются корнями из единицы. Пустьq(x) — некоторый полином над Q , степень которого меньше n. Тогда для любого корня a полинома f (x) существует не более одногонатурального решения уравнения (C.), при этом решения m уравнения (C.) для различных корней a полинома f (x) совпадают, и имеетместо оценка (C.).Несложно показать, что верны следующие утверждения:. Пусть h(x) ∈ Q и r(x) — остаток от деления h(x) на f (x).
Пустьa ∈ C, f (a) = 0. Тогда h(a) = r(a).. Пусть q1 (x), q2 (x), q3 (x), ... суть остатки от деления x, x 2 , x 3 , ...на f (x). Тогда• при k > 1 полином qk (x) равен остатку от деления xqk−1 (x) наf (x);• равенство (C.) имеет место, если и только если q(x) = qm (x).Из этих утверждений следует, что после того, как установлена граница M для возможного значения m, распознавание существованияи поиск натурального решения уравнения (C.) можно выполнить,затратив O(nM) арифметических операций над рациональными числами.Приложение CC. Неудачно выбранный размер входаОбратимся к уравнению (C.), предполагая, что среди коэффициентовунитарного неприводимого над Q полинома f (x) имеется по крайнеймере один нецелый рациональный; без специальных оговорок считаем, что корни f (x) не являются корнями из единицы.
Возникаетвопрос: можно ли и для этого случая получить подобную (C.) верхнюю оценку величины m? На протяжении ряда лет считалось, чтоответ положительный и что существует полином трех переменныхP(x1 , x2 , x3 ) такой, что даже при наличии среди коэффициентов f (x)нецелых рациональных чисел имеет место оценкаm < P(n, log2 | f |, log2 | q |),(C.)но затем выяснилось, что это неверно . Проблема заслуживает детального рассмотрения, поскольку ряд ее моментов является принципиальным. Вывод о существовании полинома P(x1 , x2 , x3 ) был сделан на основании утверждения о том, что если среди коэффициентовf (x) есть нецелые числа, то имеет место неравенствоm ¶ (n − 1) log2 | f |.(C.)Неравенство (C.) опровергается несложно (сразу заметно, что правая часть этого неравенства не зависит от вида полинома q(x), чтоподозрительно). Мы, тем не менее, сосредоточим усилия на другом — покажем, что верхняя оценка (C.) не может иметь места нетолько при полиномиальной, но и, например, при показательнойxx 3x1 2функции того или иного вида (скажем, вида 2 ) и вообще прилюбой непрерывной функции P(x1 , x2 , x3 ).
Это, в частности, лишаетвозможности характеризовать вычислительную сложность алгоритмакак полиномиальную, экспоненциальную и т. д.Указанное обстоятельство в значительной мере является следствием плохо выбранных параметров n, | f (x) | и | q(x) | размера входа.Если мы зафиксируем n и f (x), а затем будем слегка изменять значения коэффициентов полинома q(x) (тем самым два параметра размера остаются фиксированными, а третий изменяется очень мало),то при этом могут возникать уравнения вида (C.), имеющие натуральные решения m, и эти m для разных уравнений могут, как будет показано, отличаться друг от друга сколь угодно сильно. Мы укажем натуральное n, неприводимый полином f (x) ∈ Q[x] степени n,См.
[]; в этой же работе получена оценка (C.) как следствие оценки (C.).См. [].Проблема орбитпоследовательность q1 (x), q2 (x), ... ∈ Q[x] полиномов степени меньшей, чем n, и вещественные A, B, A < B, такие, что A < | qk (x) | < B,k = 1, 2, ..., и при этом каждое из уравненийam = qk (a),f (a) = 0,(C.)имеет решение m = k. Возьмемa=p3 + 4 −1,5(C.)q6p8636тогда f (x) = x 2 − x + 1, n = 2 и | f (x) | = 1 ++1=. Пусть5255b1 , b2 , ... и c1 , c2 , ...
— последовательности рациональных чисел таких,что ak = bk a + ck , и пусть qk (x) = bk x + ck ∈ Q[x] (таким образом, q(x)6равен остатку от деления x k на f (x) = x 2 − x + 1). Очевидно, что5b1 = 1, c1 = 0.Используя утверждения , , сформулированные в конце предыдущего раздела этого приложения, индукцией по k легко доказывается,что6bk+1 = bk + ck , ck+1 = −bk5для k > 0. Последняя система двух рекуррентных уравнений решается легко, так как второе уравнение позволяет заменить в первом ckна −bk−1 и получить для bk линейное рекуррентное уравнение второго порядка с постоянными коэффициентами.
В итоге имеем (см. приложение G)pp p 553 + 4 −1 k3 − 4 −1 kbk == sin(k θ )−−18554иck = −58ppp 3 − 4 −1 k −153 + 4 −1 k −1−1= − sin((k − 1)θ ),−554pгде θ ∈ R выбрано так, чтобы выполнялось a = eθ −1 . ПолучаемpÆ5p5sin2 k θ + sin2 (k − 1)θ ≤2.| qk | = bk2 + c2k =44pДля функции h(x) = sin2 x + sin2 (x − θ ) положим µ = min (h(x)) ≥ 0.0≤ x <2π4Так как sin(θ ) = , то θ не является целым кратным π, поэтому µ > 0.5Таким образом,5454| qk | = h(k θ ) ≥ µ > 0.Приложение C55pПоложим A = µ, B =2.
Для любой функции F(x1 , x2 , x3 ), непре44рывной на множествеpno86V = (x1 , x2 , x3 ): x1 = 2, x2 =, A < x3 < B ,5мы можем выбрать целое k, большее максимума функции F(x1 , x2 , x3 )на V, и это приведет к уравнению (C.) с решением m, большимF(n, | f (x) |, | q(x) |).Таким образом, нами доказана следующая теорема.Теорема C.. Пусть алгоритм распознавания существования и поиска решения m уравнения (C.) состоит в получении верхней границы M для m и в последующей проверке всех значений m = 1, 2, ..., M.Тогда сложность этого алгоритма по числу таких проверок не допускает оценки сверху вида F(n, | f (x) |, | q(x) |), где F — какая-либо непрерывная функция трех переменных.Отсутствие непрерывной функции, ограничивающей затраты, является, как уже упоминалось, следствием неудачно выбранных параметров размера входа.
Можно показать , что если среди коэффициентов унитарного неприводимого полинома f (x) имеется хотя быодин, не являющийся целым рациональным, и если C, D ∈ Z таковы,что Ca является целым алгебраическим для любого корня a полиномаf (x) и Dq(x) ∈ Z[x], то для решения m уравнения (C.) выполненоm ¶ (n − 1) log2 C + log2 D.(C.)Границы (C.) и (C.) приводят к алгоритму решения проблемыорбит.В качестве C может быть взято наименьшее общее кратное знаменателей коэффициентов полинома f (x), в качестве D — наименьшееобщее кратное знаменателей коэффициентов полинома q(x).Неверно, что C всегда можно взять меньшим , чем | f (x) |.
В этом65можно убедиться, вернувшись к f (x) = x 2 − x + 1.См. уже упоминавшуюся работу [].В [] авторы исходили из предположения, что всегда можно взять C < | f (x) |.Приложение DОптимальность схемы ГорнераТеорема D.. Пусть n — произвольное неотрицательное целое число. Не существует алгоритма, который, используя только сложение,вычитание и умножение, позволяет вычислять значениеan x n + ... + a1 x + a0(D.)по числам x, a0 , a1 , ..., an так, что количество сложений или умножений всегда оказывается меньше n.В терминах нижних границ это утверждение можно, очевидно,переформулировать следующим образом.Пусть P — класс алгоритмов, вычисляющих значение (D.) с помощью операций сложения, вычитания и умножения.
Будем рассматривать число n как размер входа x, a0 , a1 , ..., an . Тогда n является нижней границей как аддитивной сложности (измеряемой числом сложений и вычитаний в худшем случае), так и мультипликативной сложности (измеряемой числом умножений в худшем случае) алгоритмовкласса P .Несколько предварительных соглашений и замечаний. Во-первых,будем для определенности считать, что все коэффициенты полинома, а также значение x принадлежат полю рациональных чисел Q,хотя достаточно было бы потребовать, например, чтобы они принадлежали произвольному бесконечному полю. Во-вторых, ограничимсяоперациями сложения и умножения; позднее мы покажем, что привлечение вычитаний не является существенным. В-третьих, заметим,что любой алгоритм, который использует только операции сложенияи умножения и который вычисляет значение произвольного полинома фиксированной степени n по заданному x, можно записать в виделинейной (неветвящейся) программы, одной и той же для всех полиномов степени n (так как в используемом наборе операций нетопераций сравнения).
В качестве программных переменных мы будем использовать p с тем или иным целым индексом. Шагом про-Приложение Dграммы является некоторое присваивание. Подготовительный разделпрограммы содержит присваиванияp−n−1 := an ;...;p−1 := a0 ;p0 := x(D.)и, возможно, ряд присваиваний вида pk := ..., k < −n − 1, с конкретными числами в правой части (т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
