Euklidesowy TSP w NP i złożoność pierwiastka kwadratowego

W notatkach z wykładu Oli Svensson: http://theory.epfl.ch/osven/courses/Approx13/Notes/lecture4-5.pdf mówi się, że nie wiemy, czy Euclidean TSP jest w NP:

Powodem jest to, że nie wiemy, jak skutecznie obliczać pierwiastki kwadratowe.

Z drugiej strony jest ten artykuł Papadimitriou: http://www.sciencedirect.com/science/article/pii/0304397577900123, który mówi, że jest NP-kompletny, co oznacza również, że jest w NP. Chociaż nie udowodnił tego w gazecie, myślę, że uważa członkostwo w NP za trywialne, jak to zwykle bywa z takimi problemami.

Jestem tym zmieszany. Szczerze mówiąc, stwierdzenie, że nie wiemy, czy Euclidian TSP jest w NP, zszokowało mnie, ponieważ po prostu założyłem, że jest to trywialne - biorąc trasę TSP za certyfikat, możemy łatwo sprawdzić, czy jest to ważna trasa. Problem polega jednak na tym, że mogą istnieć pierwiastki kwadratowe. Notatki z wykładu zasadniczo twierdzą, że nie możemy w czasie wielomianowym rozwiązać następującego problemu:

Biorąc pod uwagę liczbę wymierną , zdecyduj, czy $q_1,\ldots,q_n,A\in\mathbb{Q}$.$\sqrt{q_1}+\cdots+\sqrt{q_n}\leq A$

Pytanie 1: Co wiemy o tym problemie?

To powoduje następujące uproszczenie, którego nie udało mi się znaleźć:

Pytanie 2: Czy można to sprowadzić do specjalnego przypadku, gdy ? Czy ten szczególny przypadek wielomianowy można rozwiązać?$n=1$

Myśląc o tym przez chwilę, doszedłem do tego. Chcemy wielomianowej złożoności czasu w odniesieniu do liczby bitów danych wejściowych, tj. Nie wielkości samych liczb. Możemy łatwo obliczyć sumę do wielomianowej liczby cyfr dziesiętnych. Aby uzyskać zły przypadek, potrzebujemy wystąpienia dla k = 1 , 2 , … takiego, że dla każdego wielomianu p istnieje liczba całkowita k taka, że $q_{1,k},\ldots,q_{n,k},A_k\in\mathbb{Q}$$k=1,2,\ldots$$p$$k$ orazAkzgadzają się co do pierwszychcyfrp(wielkości wejściowej)rozszerzenia dziesiętnego.$\sqrt{q_{1,k}}+\cdots+\sqrt{q_{n,k}}$$A_k$$p(\text{input-size})$

Pytanie 3: Czy istnieje taki przykład liczby wymiernej?

Ale jaki jest ? Zależy to od sposobu przedstawienia liczb wymiernych! Teraz jestem ciekawy:$\text{input-size}$

Pytanie 4: Czy jest algorytm ważne, jeśli liczba wymierna podano jako stosunek dwóch całkowitej (na przykład ), albo w rozwoju dziesiętnych (takie jak 2.5334 ¯ 567 )? Innymi słowy, czy istnieje rodzina liczb wymiernych, tak że wielkość rozwinięcia dziesiętnego nie jest wielomianowo ograniczona wielkością reprezentacji stosunku lub odwrotnie?$24/13$$2.5334\overline{567}$

$n$$n$

$n=1$$q \le A^2$

$a_1, \ldots, a_k, b_1, \ldots, b_k$$1$$n$$| \sum_{i = 1}^k \sqrt{a_i} - \sum_{i = 1}^k \sqrt{b_i}| = O(n^{-2k + 3/2})$$\Omega(2k\log n)$$k$

Pytanie 4 Myślę, że reprezentacja dziesiętna może być dość nieefektywna. Długość okresu to multiplikatywny rząd 10 modułów mianownika, który może być wykładniczy w liczbie bitów mianownika.

Napisałeś:

Z drugiej strony jest ten artykuł Papadimitriou: http://www.sciencedirect.com/science/article/pii/0304397577900123, który mówi, że jest NP-kompletny, co oznacza również, że jest w NP. Chociaż nie udowodnił tego w gazecie, myślę, że uważa członkostwo w NP za trywialne, jak to zwykle bywa z takimi problemami.

Dlaczego po prostu nie przeczytasz gazety, zamiast wysyłać takie bzdury? Na stronie 239 Papadimitriou dokładnie omawia te kwestie i określa swój podstawowy wariant metryki euklidesowej dla swojego dowodu.