Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше
Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике
Может ли нуль п комплексных полиномиальных уравнений относительно п неизвестных быть приблизительно найден в среднем за полиномиальное время с помощью общего алгоритма?
Последняя теорема в работе, выполненной мной совместно с Майком Шубом (см. [56]), является как раз этим результатом, но без требования общности алгоритма.
Рассмотрим определения. Пусть отображение $f: \mathbb{C}^{n} \rightarrow \mathbb{C}^{n}, f(z)=$ $=\left(f_{1}(z), \ldots, f_{n}(z)\right)$, и $z=\left(z_{1}, \ldots, z_{n}\right)$, где каждая функция $f_{i}-$ многочлен от $n$ переменных степени $d_{i}$.
Целесообразно функции $f_{i}$ сделать однородными многочленами, добавив новую переменную $z_{0}$. Это позволяет производить вычисления в соответствующем проективном пространстве, а затем возвратиться к исходной аффинной задаче.
Приблизительность нахождения нуля уравнений можно определить с помощью метода Ньютона, что необходимо вследствие работ Абеля, Галуа и других. Если необходимо оставаться на формальном уровне, то время
можно измерять количеством арифметических операций и сравнений ( $\leqslant$ ), используя вещественные машины (как в проблеме 3),
На пространстве функций $f$ для каждого $d=\left(d_{1}, \ldots, d_{n}\right)$ должна быть определена мера вероятности, а время алгоритма усреднено по пространству $f$. Существует ли такой алгоритм, где среднее время ограничено полиномом, зависящим от количества коэффициентов $f$ (величины входных данных)?
В [56] доказано, что такой алгоритм существует, однако алгоритмы отличаются для каждого $d$ и даже для каждой ожидаемой вероятности успеха. Общий алгоритм – это алгоритм, который независим от $d$ ( $d$ является частью входных данных).
Нахождение нулей многочленов и полиномиальных систем является одной из старейших и центральных задач математики. В этой проблеме требуется узнать, можно ли при некоторых условиях, заданных в задаче, peшить ее систематически при помощи компьютера. Если нет способа сделать это за полиномиальное время, то никакой компьютер никогда не приведет к успеху в решении данной задачи.
Более того, в последнее время появилась новая формулировка, придающая задаче нулей многочленов универсальную роль. Теорема Гильберта о нулях (как проблема разрешимости) – это вопрос о NP-полноте над любым полем (см. проблему 3).
Подобную проблему можно исс.тедовать и для действительных чисел, однако она будет значительно сложнее.
