Czy istnieje pogląd na złożoność twierdzenia Galois?

Twierdzenie Galois skutecznie mówi, że nie można wyrazić pierwiastków wielomianu stopnia> = 5 za pomocą racjonalnych funkcji współczynników i rodników - czy nie można tego odczytać, mówiąc, że biorąc pod uwagę wielomian, nie ma deterministycznego algorytmu znajdowania pierwiastków?
Zastanówmy się teraz nad pytaniem o formę: „Biorąc pod uwagę prawdziwy zakorzeniony wielomian a liczba k jest trzecim i czwartym najwyższym pierwiastkiem przynajmniej w odstępie k?” $p$ $p$

Świadectwem dowodowym dla tego pytania decyzyjnego będzie po prostu zbiór korzeni tego wielomianu i jest to krótki certyfikat, a zatem wygląda na to, że ALE nie jest twierdzeniem Galois mówiącym, że nie istnieje żaden deterministyczny algorytm do znalezienia certyfikatu dla tej decyzji pytanie? (i ta właściwość, jeśli true wyklucza dowolny algorytm decydujący o odpowiedzi na to pytanie) $NP$

Więc w jakiej klasie złożoności leży to pytanie decyzyjne?

We wszystkich pytaniach NP-zupełnych, które widziałem, zawsze dostępny jest trywialny algorytm czasu wykładniczego do ich rozwiązania. Nie wiem, czy oczekuje się, że będzie to właściwość, która zawsze powinna być prawdziwa dla wszystkich pytań NP-zupełnych. W przypadku tego pytania dotyczącego decyzji nie wydaje się to prawdą.

complexity-theory np-complete np polynomials użytkownik6818
źródło

Korzenie są certyfikatem, ale nie jest dla mnie oczywiste, że są krótkim certyfikatem (tzn. Że istnieje stały taki, że dla każdego wielomianu możesz zapisać jego pierwiastki w bitach , gdzie to liczba bitów wymagana do spisania wielomianu). Ale jeśli istnieje algorytm NP, istnieje prosty algorytm czasu wykładniczego: wystarczy wyliczyć wszystkie potencjalne certyfikaty i sprawdzić, czy którykolwiek z nich działa.

k

$k$

O (n^{k})

$O(n^k)$

n

$n$

David Richerby

Kilka komentarzy: (1) Korzenie mają wartości bezwzględne co najwyżej . (2) Sekwencje Sturm można zastosować do izolacji korzeni wielomianu. (3) Możemy sprawdzić, czy istnieją dwa pierwiastki w odległości dokładnie

, a jeśli tak, to obliczając GCD

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

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

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)$

Yuval Filmus,

@YuvalFilmus Czy którykolwiek z powyższych pomysłów może zostać wykorzystany do rozstrzygnięcia powyższego pytania decyzyjnego? Nie jest oczywiste, czy można je wykorzystać do rozstrzygnięcia tego pytania - w czasie wielomianowym?

user6818 18.04.15

„Twierdzenie Galois skutecznie mówi, że nie można wyrazić pierwiastków wielomianu stopnia> = 5 za pomocą racjonalnych funkcji współczynników i rodników - czy nie można tego odczytać, mówiąc, że biorąc pod uwagę wielomian nie ma deterministycznego algorytmu znajdowania pierwiastków? „ Nie, ponieważ algorytmy wielomianowe są silniejsze niż funkcje wymierne. Na przykład mogą dzielić przypadki, iterować, tworzyć tablice i zapętlać nad nimi itp.

sdcvvc 18.04.15

@ user6818 Twierdzenie dotyczy konkretnego modelu obliczeniowego - racjonalnych funkcji rodników. Jeśli zmienisz model, przestanie on obowiązywać. Na przykład, zgodnie z MathWorld mathworld.wolfram.com/QuinticEquation.html , możliwe jest rozwiązanie równania 5. stopnia za pomocą funkcji Jacobi theta. Jeśli nie masz nic przeciwko algorytmowi, który zwraca pierwiastek w granicach 0,01 (lub dowolnego ), twierdzenie Galois nie będzie już dyskwalifikować metody, ponieważ dowolną liczbę można aproksymować.

ϵ > 0

$\epsilon > 0$

sdcvvc 18.04.15

Odpowiedzi:

Interesujące połączenie, jednak teoria Galoisa stwierdza, że nie istnieje (spójna) metoda znajdowania pierwiastków kwintycznych za pomocą rodników , zamiast stwierdzenia, że problem ma rozwiązanie (np. Najdłuższą ścieżkę), która może wymagać czasu wielomianowego. Powiedziałbym więc, że bardziej dotyczy to nierozstrzygalności niż złożoności.

W teorii Galois stopniowo buduje się rozszerzenia grup pierwiastków równania krok po kroku (dodając jeden pierwiastek na raz). Wszystkie te grupy powinny być rozwiązywalne, w pewnym sensie nie powinno być dwuznaczności w procesie konstruowania tych rozszerzeń w innej kolejności. Istnieje pokrewne pytanie dotyczące MO dotyczące złożoności konstruowania grupy Galois równania .

Kolejne odniesienie tutaj: „OBLICZENIOWA TEORIA GALOISÓW: ODMIANOWI I WYLICZENIA ”, CLAUS FIEKER JURGEN KLUNERS $\mathbb{Q}$

Ponadto można systematycznie przedstawiać pierwiastki wielomianowej równania za pomocą rodników (gdy równanie można rozwiązać za pomocą rodników) w oparciu o konstrukcję grupy Galois równania. Ref: „Radykalna reprezentacja wielomianowych korzeni”, Hirokazu Anai Kazuhiro Yokoyama 2002

Złożoność obliczeniowa określenia, czy dana monic nierozkładalny wielomian przez liczby całkowite , jest rozpuszczalny rodnikami w Ref „wypłacalność przez rodników w czasie wielomianowym” S. Miller 1984 Landau GL $\mathbb{Z}$ $\mathbb{P}$

Ankieta dotycząca najnowszych „technik obliczania grup Galois”, Alexander Hulpke

Oczywiście, jeśli ktoś szuka dobrych algorytmów aproksymacyjnych i ich złożoności (np. Metoda Newtona lub twierdzenie Sturma), jest to nieco inne pytanie, a już opublikowana odpowiedź dostarcza więcej informacji w tym kierunku.

Nikos M.
źródło

Dzięki! Wygląda na to, że przypadkowo zadałem sobie bardzo ekscytujące pytanie!

user6818,

@ user6818, dziękuję zaktualizowana odpowiedź z więcej informacji i dalszych odniesień

Nikos M.

Zakładam, że rozważasz wielomiany ze współczynnikami całkowitymi .

Podjąłeś zły punkt wyjścia dla swoich dochodzeń; Twoim celem jest znalezienie dobrych oszacowań dla prawdziwych korzeni. Poszukiwanie formuły algebraicznej umożliwiającej jej ocenę z wystarczającą precyzją to coś, co możesz zrobić, ale tak naprawdę nie jest to właściwe. (chyba że k„jeden z największych rzeczywistych pierwiastków wielomianu” jest jedną z operacji algebraicznych)

Znacznie lepszym punktem wyjścia jest użycie twierdzenia Sturma do wyodrębnienia pierwiastków wielomianu. Następnie możesz tworzyć lepsze oszacowania za pomocą wyszukiwania binarnego, ale jeśli jest to zbyt wolne, możesz użyć metody Newtona, aby szybko uzyskać oszacowania o wysokiej precyzji.

Ale chodzi tylko o znalezienie certyfikatów. Wciąż pozostaje pytanie, jakie certyfikaty mogą istnieć.

Po pierwsze, zaznaczę, że możesz bezpośrednio obliczyć, czy dwa z pierwiastków są dokładnie jednostek od siebie, np. . Będziesz także musiał zdecydować, co chcesz zrobić z powtarzającymi się korzeniami i odpowiednio sobie z tym poradzić. Zakładam, że zajmujesz się tymi sprawami specjalnie. $k$ $\gcd(p(x), p(x-k))$

Jeśli wiemy, że dwa pierwiastki nie różnią się dokładnie od siebie w jednostkach , oznacza to, że możesz uzyskać oszacowanie o wystarczającej precyzji, aby udowodnić, że są one większe lub mniejsze niż jednostek od siebie. np. istnieją dwa rodzaje certyfikatów: $k$ $k$

Pierwszy rodzaj (dowód negatywny) to

$a$ nie jest pierwiastkiem z $p$
$p$ nie ma korzeni w $(a-k, a)$
$p$ ma trzy pierwiastki w $(a, \infty)$

Drugi rodzaj (dowód pozytywny) to

$a$ nie jest pierwiastkiem z $p$
$p$ ma co najmniej dwa pierwiastki w $(a-k,a)$
$p$ ma dwa pierwiastki w $(a, \infty)$

Certyfikat można zweryfikować za pomocą twierdzenia Sturma. Teraz Twoje pytanie o wielkości świadectwa sprowadza się do stwierdzenia, ile bitów precyzji trzeba reprezentować . $a$

Innymi słowy, jakie są granice możliwych wartości , gdzie są pierwiastkami ? $a-b-k$ $a,b$ $f$

Nie jestem pewien doskonałego podejścia, ale jednym, który powinien ci coś dać, jest zaobserwowanie, że wszystkie te wartości są pierwiastkami wielomianu:

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

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

Dlaczego? Przypomnijmy, że wypadkowa dwóch monomicznych wielomianów jest iloczynem wszystkich różnic ich korzeni, więc

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))$

gdzie jest współczynnikiem wiodącym, a jest stopniem . (może napisałem formułę dla zamiast ; nigdy nie jestem pewien co do znaku) $c$ $d$ $f$ $-g(x)$ $g(x)$

Zatem pytanie polega na znalezieniu szacunków dotyczących tego, jak duże mogą być współczynniki , a następnie, gdy się o tym dowiesz, znajdź oszacowania, jak blisko pierwiastka może być zero. $g$ $g$

(lub, alternatywnie, znajdź największą wielkość, jaką może mieć pierwiastek odwrotnego wielomianu ; pierwiastki odwrotnego wielomianu są odwrotnością pierwiastków ) $g$ $g$

źródło

Czy są tutaj jakieś problemy z reprezentacją danych? NP zasadniczo dotyczy maszyn Turinga i nie jest od razu oczywiste, w jaki sposób odnosi się to do liczb rzeczywistych lub liczby bitów wymaganych do spisania uzasadnień o wystarczającej precyzji. (Przykro mi, że nie jestem zbyt konstruktywny: wiem wystarczająco dużo, aby wiedzieć, że to może być problem, ale nie dość, aby wiedzieć, czy to naprawdę jest problem, a jeśli tak, to jak go rozwiązać.)

David Richerby

@DavidRicherby: Zakładam, że wejścia są zasadniczo tylko współczynniki wielomianu pisemnej w systemie binarnym, a moje oczekiwanie, że liczba bitów trzeba reprezentować binarnie będą rozgraniczone wielomianu funkcji liczby bitów Wejście. Jeśli użyjemy dwóch parametrów, liczby bitów wejściowych i stopnia wielomianu, to jestem prawie pewien, że liczba bitów potrzebnych do

będzie wielomianowa w liczbie bitów wejściowych, ale jestem mniejszy pewnie, jak to będzie zależeć od stopnia.

a

$a$

a

$a$

Dane wejściowe jako lista współczynników mają sens. Ale twoje założenia dotyczące precyzji potrzebnej do przedstawienia korzeni zdecydowanie muszą zostać sprawdzone. Na przykład powodem, dla którego dziesiąty problem Hilberta (rozwiązywanie równań diofantycznych) jest nierozstrzygalny, jest zasadniczo taki, że nie można ograniczyć długości rozwiązania pod względem długości danych wejściowych. Nie ma to tutaj bezpośredniego zastosowania, ponieważ mamy tylko jedną zmienną i nie szukamy rozwiązań całkowitoliczbowych, ale stawia to dość duże pytanie o założenie ograniczenia.

David Richerby,

@David: Teoria prawdziwych zamkniętych pól jest zupełnie inna niż teoria liczb; intuicja dotycząca jednego nie przekłada się zbyt dobrze na drugi.

Co jeśli dwa pierwiastki są osobno lub osobno? Ustalenie wystarczającej precyzji może być trudne.

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

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

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

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

Yuval Filmus,

Postaram się odpowiedzieć na pytania w większości otwarte. dowód galois znany obecnie jako Thom Abla-Ruffiniego pokazuje niemożność rozwiązania wielomianów kwintyce. (w przeciwieństwie do np. równania kwadratowego). więc nie jest to tak naprawdę wynikiem twardości problemu jako takiego, ale raczej niemożliwością . w tym sensie jest bardziej analogiczny do np. dowodu nierozstrzygalności problemu zatrzymania. teoria złożoności dotyczy ogólnie „kosztów” rozwiązań komputerowych. taki jest punkt widzenia dwóch wiodących badaczy CS w części wstępnej tego artykułu ( Obliczalność i złożoność / Kleinberg i Papadimitriou), rozdział 1 Poszukiwanie kwintycznej formuły:

Patrząc z bezpiecznej odległości kilku stuleci, historia wyraźnie opowiada o rywalizacji i zawiera wiele kluczowych składników, które powstają w późniejszych próbach modelowania obliczeń: bierzemy proces obliczeniowy, który rozumiemy intuicyjnie (rozwiązując równanie , w tym przypadku), sformułuj dokładny model i na podstawie tego modelu wyciągnij bardzo nieoczekiwane konsekwencje dotyczące mocy obliczeniowej procesu. Właśnie takie podejście chcemy zastosować do obliczeń w ogóle.

$\neq$ $\neq$

vzn
źródło

Nie jestem pewien, czy problem zatrzymania jest dobrą analogią, ponieważ bardziej przypomina „nie można obliczyć odpowiedzi”, a nie „w ogóle nie ma odpowiedzi”.

Czy twierdzenie Galois nie jest wynikiem obliczeniowej niemożliwości, tak jak problem Haltinga?

user6818,