Euclidean TSP in NP and square root complexity

Question

In this lecture notes by Ola Svensson: http://theory.epfl.ch/osven/courses/Approx13/Notes/lecture4-5.pdf, it is said that we don't know if Euclidean TSP is in NP:

The reason being that we do not know how to calculate square roots efficiently.

On the other hand there is this paper by Papadimitriou: http://www.sciencedirect.com/science/article/pii/0304397577900123 saying it is NP-complete, which also means it is in NP. Although he doesn't prove it in the paper, I think he consider the membership in NP trivial, as is usually the case with such problems.

I am confused by this. Honestly, the claim that we don't know if Euclidian TSP is in NP shocked me, since I just assumed it is trivial -- taking the TSP tour as a certificat, we can easily check it is valid tour. But the problem is that there can be some square roots. So the lecture notes basically claim that we cannot in polynomial time solve the following problem:

Given rational number $q_1,\ldots,q_n,A\in\mathbb{Q}$, decide if $\sqrt{q_1}+\cdots+\sqrt{q_n}\leq A$.

Question 1: What do we know about this problem?

This begs the following simplification, which I was unable to find:

Question 2: Is this reducible to the special case when $n=1$? Is this special case polynomial-time solvable?

Thinking about it for a while, I came to this. We want polynomial time complexity with respect to the number of bits of the input, i.e., not the size of the numbers themselves. We can easily work out the sum to a polynomial number of decimal digits. To get a bad case, we need an instance of $q_{1,k},\ldots,q_{n,k},A_k\in\mathbb{Q}$ for $k=1,2,\ldots$ such that for every polynomial $p$, there exist an integer $k$ such that $\sqrt{q_{1,k}}+\cdots+\sqrt{q_{n,k}}$ and $A_k$ agree on the first $p(\text{input-size})$ digits of decimal expansion.

Question 3: Is there such an instance of reational number?

But what is $\text{input-size}$? This depends on the way the rational numbers are represented! Now I am curious about this:

Question 4: Is is algorithmically important if rational number are given as ratio of two integer (such as $24/13$) or in the decimal expansion (such as $2.5334\overline{567}$)? In other words, is there a family of rational numbers such that the size of decimal expansion is not polynomially bounded in the size of ratio representation or the other way around?

Answer 1

Q1. This is a notorious open problem. It is known to be in the fourth level of the counting hierarchy, due to [ABKM]. Not known to be in NP. The problem is not really in computing square roots as claimed in the lecture notes: $n$ bits of a square root of an integer can be computed in time polynomial in $n$ and the bitsize of the integer. The problem is, rather, how close the sum of square roots of integers can get to an integer, without actually being integral.

Q2. The $n=1$ case is of course easy. It's the same as $q \le A^2$, which is in polynomial time, because squaring a rational number is in polynomial time.

Q3. According to this page, the best that's known is that there are integers $a_1, \ldots, a_k, b_1, \ldots, b_k$, all between $1$ and $n$, such that $| \sum_{i = 1}^k \sqrt{a_i} - \sum_{i = 1}^k \sqrt{b_i}| = O(n^{-2k + 3/2})$. This is a lower bound of $\Omega(2k\log n)$ on the number of bits needed to be computed for the potentially harder problem which allows negative coefficients. The best upper bound on the number of bits is exponential in $k$.

Q4. I think the decimal representation could be quite inefficient. The length of the period is the multiplicative order of 10 modulo the denominator, which can be exponential in the number of bits of the denominator.

Answer 2

You wrote:

On the other hand there is this paper by Papadimitriou: http://www.sciencedirect.com/science/article/pii/0304397577900123 saying it is NP-complete, which also means it is in NP. Although he doesn't prove it in the paper, I think he consider the membership in NP trivial, as is usually the case with such problems.

Why don't you simply read the paper, instead of posting such nonsense claims? On page 239, Papadimitriou carefully discusses these issues and defines the underlying variant of the Euclidean metric for his proof.