Euklidisches TSP in NP und Quadratwurzelkomplexität

In diesem Skript von Ola Svensson: http://theory.epfl.ch/osven/courses/Approx13/Notes/lecture4-5.pdf heißt es, dass wir nicht wissen, ob der euklidische TSP im NP ist:

Der Grund dafür ist, dass wir nicht wissen, wie man Quadratwurzeln effizient berechnet.

Auf der anderen Seite gibt es dieses Papier von Papadimitriou: http://www.sciencedirect.com/science/article/pii/0304397577900123, das besagt, dass es NP-vollständig ist, was auch bedeutet, dass es in NP ist. Obwohl er es in der Zeitung nicht beweist, denke ich, dass er die Mitgliedschaft in NP für trivial hält, wie es bei solchen Problemen normalerweise der Fall ist.

Das verwirrt mich. Ehrlich gesagt hat mich die Behauptung, dass wir nicht wissen, ob Euclidian TSP in NP ist, geschockt, da ich nur angenommen habe, dass es trivial ist - wenn wir die TSP-Tour als Zertifikat nehmen, können wir leicht überprüfen, ob sie gültig ist. Das Problem ist jedoch, dass es einige Quadratwurzeln geben kann. Die Vorlesungsunterlagen behaupten also grundsätzlich, dass wir das folgende Problem in der Polynomzeit nicht lösen können:

Wenn die rationale Zahl , entscheiden Sie, ob .$q_1,\ldots,q_n,A\in\mathbb{Q}$$\sqrt{q_1}+\cdots+\sqrt{q_n}\leq A$

Frage 1: Was wissen wir über dieses Problem?

Dies führt zu folgender Vereinfachung, die ich nicht finden konnte:

Frage 2: Ist dies auf den Sonderfall mit ? Ist dieser Sonderfall polynomialzeitlösbar?$n=1$

Als ich eine Weile darüber nachdachte, kam ich dazu. Wir wollen eine polynomielle Zeitkomplexität in Bezug auf die Anzahl der Bits der Eingabe, dh nicht die Größe der Zahlen selbst. Wir können die Summe leicht zu einer Polynomzahl von Dezimalstellen berechnen. Um einen schlechten Fall zu bekommen, brauchen wir eine Instanz von für k = 1 , 2 , ..., so dass für jedes Polynom p eine ganze Zahl k existiert , die $q_{1,k},\ldots,q_{n,k},A_k\in\mathbb{Q}$$k=1,2,\ldots$$p$$k$ undAkstimmen mit den erstenp-Stellen(Eingabegröße)der Dezimalerweiterungüberein.$\sqrt{q_{1,k}}+\cdots+\sqrt{q_{n,k}}$$A_k$$p(\text{input-size})$

Frage 3: Gibt es eine solche Instanz der Referenznummer?

Aber was ist die ? Dies hängt davon ab, wie die rationalen Zahlen dargestellt werden! Jetzt bin ich neugierig:$\text{input-size}$

Frage 4: I ist algorithmisch wichtig , wenn rationale Zahl als Verhältnis von zwei Integer - gegeben ist (wie beispielsweise ) oder in der Dezimaldarstellung (wie 2,5334 ¯ 567 )? Mit anderen Worten, gibt es eine Familie rationaler Zahlen, bei der die Größe der Dezimalexpansion nicht polynomiell an die Größe der Verhältnisrepräsentation gebunden ist, oder umgekehrt?$24/13$$2.5334\overline{567}$

Q1. Dies ist ein berüchtigtes offenes Problem. Es ist bekannt , in der vierten Ebene der sein Zählen Hierarchie aufgrund [ABKM] . Nicht bekannt, dass er in NP ist. Das Problem liegt nicht wirklich in der Berechnung der Quadratwurzeln, wie in den Vorlesungssätzen behauptet: Bits einer Quadratwurzel einer ganzen Zahl können in Zeitpolynom in n und der Bitgröße der ganzen Zahl berechnet werden . Das Problem ist vielmehr, wie nahe die Summe der Quadratwurzeln von ganzen Zahlen einer ganzen Zahl kommen kann, ohne tatsächlich ganzzahlig zu sein.$n$$n$

Q2. Der Fall ist natürlich einfach. Es ist dasselbe wie q ≤ A 2 , was in Polynomzeit ist, weil das Quadrieren einer rationalen Zahl in Polynomzeit ist.$n=1$$q \le A^2$

Q3. Nach dieser Seite ist das Beste, was bekannt ist, dass es ganze Zahlen , die alle zwischen 1 und n liegen , so dass | ∑ k i = 1$a_1, \ldots, a_k, b_1, \ldots, b_k$$1$$n$. Dies ist eine Untergrenze vonΩ(2klogn)für die Anzahl der Bits, die für das möglicherweise schwierigere Problem berechnet werden müssen, das negative Koeffizienten zulässt. Die beste Obergrenze für die Anzahl der Bits ist inkexponentiell.$| \sum_{i = 1}^k \sqrt{a_i} - \sum_{i = 1}^k \sqrt{b_i}| = O(n^{-2k + 3/2})$$\Omega(2k\log n)$$k$

Q4. Ich denke, die Dezimaldarstellung könnte ziemlich ineffizient sein. Die Länge der Periode ist die multiplikative Ordnung von 10 Modulo des Nenners, die in der Anzahl der Bits des Nenners exponentiell sein kann.

Sie schrieben:

Auf der anderen Seite gibt es dieses Papier von Papadimitriou: http://www.sciencedirect.com/science/article/pii/0304397577900123, das besagt, dass es NP-vollständig ist, was auch bedeutet, dass es in NP ist. Obwohl er es in der Zeitung nicht beweist, denke ich, dass er die Mitgliedschaft in NP für trivial hält, wie es bei solchen Problemen normalerweise der Fall ist.

Warum liest du nicht einfach die Zeitung, anstatt solche Unsinnsprüche zu posten? Papadimitriou erörtert diese Fragen sorgfältig und definiert für seinen Beweis die zugrunde liegende Variante der euklidischen Metrik.