Есть ли сложная точка зрения теоремы Галуа?

Теорема Галуа эффективно говорит, что нельзя выразить корни многочлена степени> = 5, используя рациональные функции коэффициентов и радикалов - разве нельзя считать, что это говорит о том, что для данного многочлена нет детерминированного алгоритма для нахождения корней?
Теперь рассмотрим вопрос решения в форме: «Учитывая действительный корень полинома $p$ и число k является третьим и четвертым наивысшим корнем $p$ по крайней мере на промежутке k?»

Сертификат доказательства для этого вопроса о решении будет просто набором корней этого многочлена, и это будет короткий сертификат, и, следовательно, похоже, что $NP$ НО не является теоремой Галуа, говорящей о том, что не существует какого-либо детерминированного алгоритма для поиска сертификата для этого решение вопроса? (и это свойство, если true, исключает любой алгоритм, чтобы решить ответ на этот вопрос)

Так в каком классе сложности находится этот вопрос решения?

Все NP-полные вопросы, которые я видел, всегда имеют тривиальный экспоненциальный алгоритм времени, доступный для их решения. Я не знаю, ожидается ли, что это будет свойство, которое всегда должно быть правдой для всех NP-полных вопросов. Для этого вопроса решения это не похоже на правду.

complexity-theory np-complete np polynomials user6818
источник

Корни сертификат , но это не для меня очевидно , что они в короткий сертификат (то есть, что существует константа

такая , что для любого многочлена, вы можете написать свои корни в

битов, где

есть количество битов, необходимых для записи полинома). Но если есть алгоритм NP, существует тривиальный алгоритм экспоненциального времени: просто перечислите все потенциальные сертификаты и посмотрите, работает ли какой-либо из них.

k

$k$

O (n^{k})

$O(n^k)$

n

$n$

Дэвид Ричерби

Несколько комментариев: (1) Корни

имеют абсолютные значения не более

\sum_{i = 0}^{n} a_{i} x_{i}

$\sum_{i=0}^n a_i x_i$

. (2) Последовательности Штурма могут быть использованы для выделения корней многочлена. (3) Мы можем проверить, есть ли два корня на расстоянии точно

, и если да, то, вычисляя GCD

max (1, \sum_{i = 0}^{n - 1} | a_{i} | / | a_{n} |)

$\max(1,\sum_{i=0}^{n-1} |a_i|/|a_n|)$

k

$k$

p (x)

$p(x)$

p (x + k)

$p(x+k)$

Юваль Фильмус

@YuvalFilmus Можно ли использовать какие-либо из ваших идей для решения вышеуказанного вопроса? Не очевидно, могут ли они быть использованы для решения этого вопроса - за полиномиальное время?

user6818

«Теорема Галуа эффективно говорит о том, что невозможно выразить корни многочлена степени> = 5 с помощью рациональных функций коэффициентов и радикалов - нельзя ли сказать, что для данного многочлена не существует детерминированного алгоритма для нахождения корней? " Нет, поскольку алгоритмы полиномиального времени более мощные, чем рациональные функции. Например, они могут разделять

регистры

@ user6818 Теорема касается конкретной вычислительной модели - рациональных функций радикалов. Если вы измените модель, она больше не применяется. Например, согласно MathWorld mathworld.wolfram.com/QuinticEquation.html можно решить уравнение 5-й степени с использованием тэта-функций Якоби. Если вы в порядке с алгоритмом, который возвращает корень в пределах 0,01 (или любой другой

), теорема Галуа больше не будет дисквалифицировать метод, поскольку любое число может быть аппроксимировано рациональным.

ϵ > 0

$\epsilon > 0$

sdcvvc

Ответы:

Интересная связь, однако, теория Галуа утверждает, что не существует (непротиворечивого) метода для нахождения корней квинтики с использованием радикалов , вместо того, чтобы говорить, что у проблемы есть решение (например, самый длинный путь), которое может потребовать суперполиномиального времени. Так что я бы сказал, что это больше связано с неразрешимостью, чем со сложностью.

В частности, в теории Галуа постепенно строятся групповые расширения корней уравнения, шаг за шагом (добавляя один корень за раз). И все эти группы должны быть разрешимыми, в некотором смысле не должно быть никакой двусмысленности в процессе построения этих расширений в другом порядке. Существует связанный с МО вопрос о сложности построения группы Галуа уравнения .

Еще одна ссылка здесь "ВЫЧИСЛИТЕЛЬНАЯ ТЕОРИЯ ГАЛУА: ИНВАРИАНТЫ И ВЫЧИСЛЕНИЯ НАД ", КЛАУС ФИКЕР ЮРГЕН КЛУНЕРС $\mathbb{Q}$

Кроме того, можно систематически представлять корни полиномиального уравнения с использованием радикалов (когда уравнение разрешимо с использованием радикалов) на основе построения группы (групп) Галуа уравнения. Ссылка: «Радикальное представление полиномиальных корней», Хироказу Анаи Казухиро Йокояма 2002

Вычислительная сложность определения, является ли данный монический неприводимый многочлен над целыми числами , разрешима радикалами, приведена в Ref"Разрешимость радикалами за полиномиальное время", С. Ландау Г. Л. Миллер 1984 $\mathbb{Z}$ $\mathbb{P}$

Обзор недавних «Методик вычисления групп Галуа», Александр Хулпке

Конечно, если кто-то ищет хорошие алгоритмы аппроксимации и их сложность (например, метод Ньютона или теорема Штурма), это немного другой вопрос, и уже опубликованный ответ дает больше информации в этом направлении.

Никос М.
источник

Благодарность! Кажется, я случайно задал себе очень волнующий вопрос!

user6818

@ user6818, спасибо, обновил ответ с дополнительной информацией и дальнейшими ссылками

Никос М.

Я предполагаю, что вы рассматриваете полиномы с целыми коэффициентами.

Вы выбрали неверную отправную точку для своих расследований; Ваша цель - найти хорошие оценки для реальных корней. Поиск алгебраической формулы, чтобы вы могли оценить ее с достаточной точностью, - это то, что вы можете сделать, но это не совсем то, что нужно делать здесь. (если, конечно, « k-ый по величине вещественный корень многочлена» не является одной из ваших алгебраических операций)

Намного лучше начать с использования теоремы Штурма для выделения корней многочлена. Затем вы можете получить более точные оценки с помощью бинарного поиска, но если это слишком медленно, вы можете использовать метод Ньютона для быстрого получения оценок с высокой точностью.

Но это только поиск сертификатов. Остается вопрос о том, какие сертификаты могут существовать.

Прежде всего, я укажу, что вы можете напрямую вычислить, находятся ли два корня точно на единицах, например, вычисляя . Вам также нужно будет решить, что вы хотите делать с повторяющимися корнями, и действовать соответствующим образом. Я предполагаю, что вы будете иметь дело с этим делом специально. $k$ $\gcd(p(x), p(x-k))$

Если мы знаем, что два корня не находятся точно в единицах, это означает, что вы можете получить оценку с достаточной точностью, чтобы доказать, что они либо больше, либо меньше, чем единиц. например, есть два вида сертификатов: $k$ $k$

Первый вид (доказательство в отрицании)

не корень $a$ $p$
не имеет корней в $p$ $(a-k, a)$
имеет три корня в $p$ $(a, \infty)$

Второй вид (доказательство в позитиве)

не корень $a$ $p$
имеет по крайней мере два корня в $p$ $(a-k,a)$
имеет два корня в $p$ $(a, \infty)$

Сертификат можно проверить с помощью теоремы Штурма. Теперь, ваш вопрос о размере сертификата сводится к нахождению , сколько битов точности нужно представлять . $a$

Другими словами, каковы границы возможных значений , где - корни из ? $a-b-k$ $a,b$ $f$

Я не уверен в отличном подходе, но тот, который должен дать вам кое-что, должен заметить, что все эти значения являются корнями полинома:

g (x) = {Res}_{y} (f (y), f (x + y + k))

$g(x) = \mathop{\text{Res}_y}(f(y), f(x + y + k))$

Почему? Напомним, что результат двух моничных многочленов является произведением всех разностей их корней, поэтому

g (x) = c^{d^{2}} \prod_{a, b} (b - (a - x - k)) = \prod_{a, b} (x - (a - b - k))

$g(x) = c^{d^2} \prod_{a,b}(b - (a - x - k)) = \prod_{a,b} (x - (a-b-k))$

где - ведущий коэффициент, а - степень . (возможно я написал формулу для вместо $c$ $d$ $f$ $-g(x)$ $g(x)$ ; я никогда не уверен в знаке)

Поэтому вопрос состоит в том, чтобы найти оценки того, насколько большими могут быть коэффициенты , а затем, как только вы это узнаете, найти оценки того, насколько близок корень из $g$ $g$ к нулю.

(или, альтернативно, найдите наибольшую величину, которую может иметь корень обратного полинома от ; корни обратного полинома являются обратными корням из ) $g$ $g$

источник

Есть ли здесь какие-либо проблемы с представлением данных? NP в основном относится к машинам Тьюринга, и не сразу видно, как это соотносится с действительными числами или количеством битов, необходимых для записи рациональных чисел с достаточной точностью. (Мне жаль, что я не очень конструктивен: я знаю достаточно, чтобы понять, что это может быть проблемой, но недостаточно, чтобы понять, действительно ли это проблема или, если да, то как ее решить.)

Дэвид Ричерби,

@DavidRicherby: Я предполагаю , что входы в основном только коэффициенты полинома написанном в двоичном, и мое ожидание, что число битов , вы должны представлять в двоичной системе будет ограничено полиномиальной функцией от числа битов вход. Если мы используем два параметра, количество входных битов и степень полинома, то я почти уверен, что количество бит, которое вам нужно для

будет полиномиальным по количеству входных бит, но я меньше точно, как это будет зависеть от степени.

a

$a$

a

$a$

Ввод в виде списка коэффициентов имеет смысл. Но ваши предположения о точности, необходимой для представления корней, безусловно, необходимо проверить. Например, причина того, что десятая проблема Гильберта (решение диофантовых уравнений) неразрешима, заключается в том, что вы не можете ограничить длину решения в терминах длины входных данных. Здесь это не применимо напрямую, поскольку у нас есть только одна переменная, и мы не ищем целочисленных решений, но она задает довольно большой вопрос о допущении ограниченности.

Дэвид Ричерби

@ Дэвид: теория реальных замкнутых полей резко отличается от теории чисел; интуиция об одном не очень хорошо переходит к другому.

k + 2^{- 2^{2^{n}}}

$k+2^{-2^{2^n}}$

k - 2^{- 2^{2^{n}}}

$k-2^{-2^{2^n}}$

собираюсь принять ваши вопросы, как в основном открытые. доказательство Галуа, теперь известное как Абель-Раффини, показывает невозможность полиномиальных решений квинтики. (в отличие, например, от квадратного уравнения). поэтому его на самом деле не в результате на твердость проблемы как таковой , а скорее невозможности . в этом смысле это более аналогично, например, доказательству неразрешимости проблемы остановки. Теория сложности в целом связана с «стоимостью» вычислительных решений. это точка зрения двух ведущих исследователей CS во вводном разделе этой следующей статьи ( вычислимость и сложность / Kleinberg & Papadimitriou), сек. 1 Поиски формулы квинтов:

Если смотреть с безопасного расстояния в несколько веков, история, очевидно, посвящена компьютерным вычислениям и содержит много ключевых компонентов, которые возникают в последующих попытках смоделировать вычисления: мы берем вычислительный процесс, который мы понимаем интуитивно (решение уравнения (в данном случае), сформулировать точную модель, и из модели вывести некоторые весьма неожиданные последствия в отношении вычислительной мощности процесса. Именно этот подход мы хотим применить к вычислениям в целом.

$\neq$ $\neq$

ВЗН
источник

Я не уверен, что проблема остановки - хорошая аналогия, так как она больше похожа на «вы не можете вычислить ответ», а не «нет ответа вообще».

Разве теорема Галуа не является результатом вычислительной невозможности, как проблема Остановки?

user6818