Suma rodników
W teorii złożoności obliczeniowej istnieje otwarty problem, czy pewne informacje o sumie pierwiastków mogą być obliczane w czasie wielomianowym w zależności od rozmiaru danych wejściowych, tj. liczby bitów potrzebnych do przedstawienia tej sumy. Ma to znaczenie dla wielu problemów geometrii obliczeniowej , ponieważ obliczenie odległości euklidesowej między dwoma punktami w ogólnym przypadku obejmuje obliczenie pierwiastka kwadratowego , a zatem obwodu wielokąta lub długość łańcucha wielokątnego przyjmuje postać sumy rodników.
Suma rodników jest zdefiniowana jako skończona liniowa kombinacja rodników:
![{\displaystyle \sum _{i=1}^{n}k_{i}{\sqrt[{r_{i}}]{x_{i}}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/88f8e5154b52c32759c00bcfd8940b97ad925b4f)
gdzie są liczbami naturalnymi i są liczbami rzeczywistymi .
Większość badań teoretycznych z zakresu geometrii obliczeniowej o charakterze kombinatorycznym zakłada model obliczeniowy rzeczywistej pamięci RAM o nieskończonej precyzji, czyli abstrakcyjnego komputera , w którym liczby rzeczywiste i operacje na nich są wykonywane z nieskończoną precyzją i wielkością wejściową liczby rzeczywistej oraz kosztem operacja elementarna to stałe. Istnieją jednak badania nad złożonością obliczeniową, zwłaszcza w algebrze komputerowej , gdzie rozmiarem wejściowym liczby jest liczba bitów niezbędnych do jej reprezentacji.
Szczególnie interesujący w geometrii obliczeniowej jest problem wyznaczania znaku sumy pierwiastków . Na przykład długość wielokątnej ścieżki, w której wszystkie wierzchołki mają współrzędne całkowite, można wyrazić za pomocą twierdzenia Pitagorasa jako sumę całkowitych pierwiastków kwadratowych, więc w celu ustalenia, czy jedna ścieżka jest dłuższa, czy krótsza niż inna w najkrótszej euklidesowej ścieżce problem, konieczne jest wyznaczenie znaku wyrażenia, w którym długość pierwszej ścieżki jest odejmowana od długości drugiej; to wyrażenie jest sumą rodników.
W podobny sposób problem sumy rodników jest nieodłącznym elementem problemu triangulacji minimalnej wagi w metryce euklidesowej .
W 1991 roku Blömer zaproponował algorytm Monte Carlo w czasie wielomianowym do określania, czy suma rodników wynosi zero , czy bardziej ogólnie, czy reprezentuje liczbę wymierną. Chociaż wynik Blömera nie rozwiązuje obliczeniowej złożoności znajdowania znaku sumy pierwiastków, oznacza to, że jeśli ten ostatni problem jest w klasie NP , to jest również w ko-NP .