Евклидова TSP в NP и сложности квадратного корня

В этой лекционной заметке Олы Свенссон: http://theory.epfl.ch/osven/courses/Approx13/Notes/lecture4-5.pdf говорится, что мы не знаем, находится ли евклидова TSP в NP:

Причина в том, что мы не знаем, как эффективно рассчитать квадратные корни.

С другой стороны, есть документ Пападимитриу: http://www.sciencedirect.com/science/article/pii/0304397577900123, в котором говорится, что он является NP-полным, что также означает, что он находится в NP. Хотя он не доказывает это в газете, я думаю, что он считает членство в NP тривиальным, как это обычно бывает с такими проблемами.

Я смущен этим. Честно говоря, заявление о том, что мы не знаем, находится ли Euclidian TSP в NP, потрясло меня, так как я просто предположил, что это тривиально - принимая тур TSP в качестве сертификата, мы можем легко проверить, является ли он действительным туром. Но проблема в том, что здесь могут быть квадратные корни. Таким образом, лекционные заметки в основном утверждают, что мы не можем за полиномиальное время решить следующую проблему:

Учитывая рациональное число , решить , если .$q_1,\ldots,q_n,A\in\mathbb{Q}$$\sqrt{q_1}+\cdots+\sqrt{q_n}\leq A$

Вопрос 1: Что мы знаем об этой проблеме?

Напрашивается следующее упрощение, которое мне не удалось найти:

Вопрос 2: сводится ли это к частному случаю, когда ? Разрешается ли этот частный случай за полиномиальное время?$n=1$

Подумав немного, я пришел к этому. Мы хотим, чтобы сложность за полиномиальное время зависела от количества входных бит, т. Е. Не от размера самих чисел. Мы можем легко вычислить сумму до полиномиального числа десятичных цифр. Чтобы получить плохой случай, нам нужен экземпляр для такой что для каждого полинома , существует целое число такое, что и согласовывают первые цифры десятичное расширение. k = 1 , 2 , … p k $q_{1,k},\ldots,q_{n,k},A_k\in\mathbb{Q}$$k=1,2,\ldots$$p$$k$ Akp(входной размер$\sqrt{q_{1,k}}+\cdots+\sqrt{q_{n,k}}$$A_k$$p(\text{input-size})$

Вопрос 3: есть ли такой случай с рациональным числом?

Но что такое ? Это зависит от способа представления рациональных чисел! Теперь мне интересно об этом:$\text{input-size}$

Вопрос 4: Является ли алгоритмически важным, если рациональное число задается в виде отношения двух целых чисел (например, ) или десятичного разложения (например, )? Другими словами, существует ли семейство рациональных чисел, такое, что размер десятичного разложения не ограничен полиномиально размером представления отношения или наоборот?2,5334 ¯ $24/13$$2.5334\overline{567}$

Q1. Это печально известная открытая проблема. Известно, что он находится на четвертом уровне иерархии подсчета , благодаря [ABKM] . Не известно, чтобы быть в NP. Проблема не в том, чтобы вычислить квадратные корни, как утверждается в примечаниях к лекции: бит квадратного корня из целого числа могут быть вычислены по полиному времени от и размеру целого числа в битах. Проблема, скорее, в том, насколько близко сумма квадратных корней целых чисел может получить целое число, не будучи на самом деле целочисленным.$n$$n$

Q2. случай, конечно , легко. Это то же самое, что , который находится в полиномиальном времени, потому что возведение в квадрат рационального числа находится в полиномиальном времени.q ≤ A $n=1$$q \le A^2$

Q3. Согласно этой странице , лучше всего известно, что существуют целые числа , все между и , такие что . Это нижняя граница для количества битов, которое необходимо вычислить для потенциально более сложной задачи, которая допускает отрицательные коэффициенты. Наилучшая верхняя граница числа битов экспоненциальная по . 1 n | Е K я = 1$a_1, \ldots, a_k, b_1, \ldots, b_k$$1$$n$Ω(2клогп)$| \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. Я думаю, что десятичное представление может быть довольно неэффективным. Длина периода равна мультипликативному порядку 10 по знаменателю, который может быть экспоненциальным по количеству бит знаменателя.

Вы написали:

С другой стороны, есть документ Пападимитриу: http://www.sciencedirect.com/science/article/pii/0304397577900123, в котором говорится, что он является NP-полным, что также означает, что он находится в NP. Хотя он не доказывает это в газете, я думаю, что он считает членство в NP тривиальным, как это обычно бывает с такими проблемами.

Почему бы вам просто не прочитать газету вместо того, чтобы публиковать такие глупые заявления? На странице 239 Пападимитриу тщательно обсуждает эти вопросы и определяет основной вариант евклидовой метрики для своего доказательства.