Trudne problemy z sumą pierwiastków kwadratowych?

Suma pierwiastki problemu prosi, ponieważ dwie sekwencje i dodatnich liczb całkowitych czy suma mniejszy, równy lub większy niż suma . Status złożoności tego problemu jest otwarty; zobacz ten post, aby uzyskać więcej informacji. Problem ten powstaje naturalnie w geometrii obliczeniowej, szczególnie w problemach związanych z najkrótszymi ścieżkami euklidesowymi, i stanowi znaczącą przeszkodę w przenoszeniu algorytmów tych problemów z prawdziwej pamięci RAM do standardowej pamięci RAM całkowitej. $a_1, a_2, \dots, a_n$ $b_1, b_2, \dots, b_n$ $\sum_i \sqrt{a_i}$ $\sum_i \sqrt{b_i}$

Nazwij problem Π suma-kwadrat-pierwiastek-twardy (w skrócie Σ√-twardy?), Jeśli występuje wielomianowe zmniejszenie czasu z sumy problemu pierwiastków kwadratowych do Π. Nietrudno udowodnić, że następujący problem jest sumą pierwiastków kwadratowych:

Najkrótsze ścieżki na 4d euklidesowych wykresach geometrycznych

Instancja: Wykres którego wierzchołki są punktami w , z krawędziami ważonymi przez euklidesową odległość; dwa wierzchołki i $G=(V,E)$ $\mathbb{Z}^4$ $s$ $t$

Wydajność: Najkrótsza ścieżka z z w . $s$ $t$ $G$

Oczywiście problem ten można rozwiązać w czasie wielomianowym na prawdziwej pamięci RAM za pomocą algorytmu Dijkstry, ale każde porównanie w tym algorytmie wymaga rozwiązania problemu sumy pierwiastków kwadratowych. Redukcja wykorzystuje fakt, że dowolną liczbę całkowitą można zapisać jako sumę czterech idealnych kwadratów; wyjście redukcji jest w rzeczywistości cyklem na wierzchołkach. $2n+2$

Jakie inne problemy są trudne do rozwiązania? Szczególnie interesują mnie problemy, dla których istnieje rozwiązanie wielomianowe na prawdziwej pamięci RAM. Zobacz moje poprzednie pytanie dotyczące jednej możliwości.

Jak sugeruje Robin, nudne odpowiedzi są nudne. Dla każdej klasy złożoności X, która zawiera sumę pierwiastków kwadratowych (na przykład PSPACE lub EXPTIME), każdy trudny problem z X jest nudno sumą pierwiastków kwadratowych.

ds.algorithms big-list reductions computing-over-reals Jeffε
źródło

Podziękowania dla Suresha i Petera za zasugerowanie tego pytania.

Jeffε

Być może mógłbyś również wykluczyć trywialne odpowiedzi, nalegając, aby odpowiedzi nie były tylko problemami trudnymi dla klasy, o której wiadomo, że zawiera problem sumy pierwiastków kwadratowych. Na przykład każdy problem związany z PSPACE byłby trudny do zsumowania pierwiastków kwadratowych, ale prawdopodobnie nie jest to interesujące.

Robin Kothari

Czy naprawdę masz na myśli w swoim opisie problemu z najkrótszymi ścieżkami, czy ? Ten pierwszy nie wydaje się, że mógłby w ogóle użyć całkowitej liczby pamięci RAM, i prawdopodobnie problemem jest nadal hard-trudne ograniczenie do punktów całkowitych ...

R^{4}

$\mathbb{R}^4$

Z^{4}

$\mathbb{Z}^4$

Steven Stadnicki

@Steven: Tak, masz rację. Edytowane.

Jeffε

Odpowiedzi:

Zostało to nieco omówione w poniższej ankiecie (początek slajdu 21): http://homepages.inf.ed.ac.uk/kousha/games08_tutorial.pdf

który wspomina euklidesowy TSP, przybliżenie faktycznej równowagi Nasha i mówi o klasach PosSLP i FIXP.

Noam
źródło

to fascynujące połączenie.

Suresh Venkat

To powinien być komentarz, ponieważ jest to najbardziej nudna odpowiedź, ale nie mam wystarczającej reputacji.

Problem sumy pierwiastków kwadratowych jest w z [ABKM98] , więc każdy trudny problem dla tej klasy ma wymaganą właściwość. Odbywa się to poprzez zredukowanie problemu z sumą pierwiastków kwadratowych do problemu o nazwie , zdefiniowanego jako decydowanie, czy problem z linią prostą reprezentuje dodatnią liczbę całkowitą, tak że problem jest trudny z sumą pierwiastków kwadratowych. $P^{PP^{PP^{PP}}}$ $PosSLP$

[ABKM98]: O złożoności analizy numerycznej, Allender, Burgisser, Kjeldgaard-Pedersen i Miltersen.

Abel Molina
źródło

Jest też to ulepszenie [ mpi-inf.mpg.de/~csaha/Sum_sqrroot.pdf], które umieszcza problem w a także udowadnia, że ograniczona wersja problemu wymaga wielomianowej liczby bitów.

{C o R P}^{P P}

${CoRP}^{PP}$

Elias

@Elias: Czy możesz opracować? Z pobieżnego spojrzenia Kayal i Saha dyskutują o „wersji wielomianowej” problemu sumy pierwiastków kwadratowych, która jest związana, ale różni się od zwykłej problemu sumy pierwiastków kwadratowych.

Tsuyoshi Ito

@Abel: (1) Cześć Abel, miło cię widzieć! (2) Ze względu na swoją wartość [ABKM98] faktycznie zaprezentowano na CCC 2006 i opublikowano w 2009 r . (3) Nudna odpowiedź nie powinna być komentarzem, ale należy ją zachować dla siebie. Ale nie sądzę, że to nudna odpowiedź. :)

Tsuyoshi Ito

@Tsuyoshi: Całkowicie rozwiązali wielomianową wersję problemu. Na tej podstawie dowodzą, że jeśli mają specjalną formę, tj. gdzie , i , to potrzebna jest liczba bitów wielomianu zdecydować problem.

a_{i}

$a_i$

a_{i} = \sum_{i} b_{i} j X^{d_{i} - j}

$a_i=\sum_i{b_ij}X^{d_i-j}$

X > (B + 1)^{(n d)^{O (1)}}

$X>(B+1)^{(nd)^{O(1)}}$

B = m a x {b_{i j}}

$B=max\{b_{ij}\}$

d = m a x {d_{i}}

$d=max\{d_i\}$

Elias,

@Tsuyoshi: Całkowicie źle zrozumiałem twoje pytanie. Przepraszam za to. Kayal i Saha dowodzą, że DegSLP jest w . Powinienem być bardziej ostrożny. Dziękuję Ci za to.

C o R P^{P P}

$CoRP^{PP}$

Elias