Summe der Quadratwurzel-harten Probleme?

Das Problem der Summe der Quadratwurzeln fragt bei zwei Folgen und von positiven ganzen Zahlen, ob die Summe kleiner, gleich oder größer ist als die Summe . Der Komplexitätsstatus dieses Problems ist offen. Weitere Details finden Sie in diesem Beitrag . Dieses Problem tritt natürlich in der Berechnungsgeometrie auf, insbesondere bei Problemen mit euklidischen kürzesten Wegen, und ist ein bedeutender Stolperstein beim Übertragen von Algorithmen für diese Probleme vom realen RAM zum Standard-Integer-RAM. $a_1, a_2, \dots, a_n$ $b_1, b_2, \dots, b_n$ $\sum_i \sqrt{a_i}$ $\sum_i \sqrt{b_i}$

Nennen Sie ein Problem Π Summe der Quadratwurzeln hart (abgekürzt Σ√ hart?), Wenn sich die Polynomzeit von der Summe der Quadratwurzeln auf Π verringert. Es ist nicht schwer zu beweisen, dass das folgende Problem die Summe der Quadratwurzeln ist:

Kürzeste Pfade in 4d euklidischen geometrischen Diagrammen

Instanz: Ein Graph dessen Eckpunkte Punkte in , deren Kanten mit euklidischem Abstand gewichtet sind; zwei Ecken und $G=(V,E)$ $\mathbb{Z}^4$ $s$ $t$

Ausgang: Der kürzeste Weg von nach in . $s$ $t$ $G$

Natürlich kann dieses Problem in Polynomialzeit auf dem realen RAM unter Verwendung des Dijkstra-Algorithmus gelöst werden, aber jeder Vergleich in diesem Algorithmus erfordert die Lösung eines Quadratwurzelsummenproblems. Die Reduktion verwendet die Tatsache, dass eine beliebige Ganzzahl als Summe von vier perfekten Quadraten geschrieben werden kann. Die Ausgabe der Reduktion ist tatsächlich ein Zyklus auf Eckpunkten. $2n+2$

Welche anderen Probleme sind wurzelhart? Ich interessiere mich besonders für Probleme, für die es eine polynomielle Lösung für den realen Arbeitsspeicher gibt. Siehe meine vorherige Frage für eine Möglichkeit.

Wie Robin vorschlägt, sind langweilige Antworten langweilig. Für jede Komplexitätsklasse X, die Quadratwurzelsummen enthält (z. B. PSPACE oder EXPTIME), ist jedes X-harte Problem langweilig Quadratwurzelsummen-hart.

ds.algorithms big-list reductions computing-over-reals Jeffε
quelle

Vielen Dank an Suresh und Peter, die diese Frage vorgeschlagen haben.

Jeffs

Vielleicht könnten Sie auch triviale Antworten ausschließen, indem Sie darauf bestehen, dass die Antworten nicht nur Probleme sind, die für eine Klasse schwierig sind, von der bekannt ist, dass sie das Problem der Summe der Quadratwurzeln enthält. Zum Beispiel wäre jedes PSPACE-harte Problem die Summe der Quadratwurzeln, aber das ist wahrscheinlich nicht interessant.

Robin Kothari

Meinen Sie wirklich in Ihrer Problembeschreibung für kürzeste Wege oder ? Ersteres scheint überhaupt keinen Integer-RAM zu benötigen, und vermutlich besteht das Problem immer noch darin, sich auf Integer-Punkte zu beschränken ...

R^{4}

$\mathbb{R}^4$

Z^{4}

$\mathbb{Z}^4$

Steven Stadnicki,

@Steven: Ja, du hast recht. Bearbeitet

Jeffs

Antworten:

Dies wurde in der folgenden Umfrage (beginnend mit Folie 21) ein wenig erörtert: http://homepages.inf.ed.ac.uk/kousha/games08_tutorial.pdf

Hier wird Euklidisches TSP erwähnt, die Annäherung des tatsächlichen Nash-Gleichgewichts, und es werden die Klassen PosSLP und FIXP behandelt.

Noam
quelle

Das ist eine faszinierende Verbindung.

Suresh Venkat

Dies sollte ein Kommentar sein, da es eine meist langweilige Antwort ist, aber ich habe nicht genug Ruf.

Die Summe der Quadratwurzelprobleme ergibt sich aus von [ABKM98] , sodass jedes für diese Klasse schwierige Problem die erforderliche Eigenschaft hat. Dies geschieht durch Reduzieren des Problems der Quadratwurzelsumme auf ein Problem mit der Bezeichnung , das als Entscheidung definiert ist, ob ein Problem eine positive ganze Zahl darstellt, so dass das Problem die Quadratwurzelsumme hart ist. $P^{PP^{PP^{PP}}}$ $PosSLP$

[ABKM98]: Zur Komplexität der numerischen Analyse von Allender, Burgisser, Kjeldgaard-Pedersen und Miltersen.

Abel Molina
quelle

Es gibt auch diese Verbesserung [ mpi-inf.mpg.de/~csaha/Sum_sqrroot.pdf] , die das Problem in und auch beweist, dass eine eingeschränkte Version des Problems eine polynomielle Anzahl von Bits benötigt.

{C o R P}^{P P}

${CoRP}^{PP}$

Elias

@ Elias: Kannst du das näher erläutern? Von einem flüchtigen Blick aus scheinen Kayal und Saha die „Polynomversion“ des Problems der Summe der Quadratwurzeln zu diskutieren, die mit dem Problem der Summe der Quadratwurzeln zusammenhängt, sich jedoch von diesem unterscheidet.

Tsuyoshi Ito

@Abel: (1) Hallo Abel, ich freue mich über deinen Beitrag! (2) Für das, was es wert ist, wurde [ABKM98] tatsächlich auf der CCC 2006 vorgestellt und 2009 veröffentlicht . (3) Eine langweilige Antwort sollte kein Kommentar sein, sondern für sich behalten werden. Aber ich denke nicht, dass dies eine langweilige Antwort ist. :)

Tsuyoshi Ito

@ Tsuyoshi: Sie haben die polynomische Version des Problems vollständig gelöst. Basierend darauf beweisen sie, dass wenn eine spezielle Form hat, dh wobei , und , dann brauchen wir eine polynomielle Anzahl von Bits, um das Problem zu entscheiden.

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: Ich habe deine Frage völlig falsch verstanden. Das tut mir leid. Was Kayal und Saha beweisen, ist, dass DegSLP in . Ich sollte vorsichtiger sein. Danke dafür.

C o R P^{P P}

$CoRP^{PP}$

Elias