TR23-163 Authors: Nikhil Balaji, Samir Datta

Publication: 2nd November 2023 03:44

Downloads: 238

Keywords:

The Sum of Square Roots (SSR) problem is the following computational problem: Given positive integers $a_1, \dots, a_k$, and signs $\delta_1, \dots, \delta_k \in \{-1, 1\}$, check if $\sum_{i=1}^k \delta_i \sqrt{a_i} > 0$. The problem is known to have a polynomial time algorithm on the real RAM model of computation, however, no sub-exponential time algorithm is known in the bit or Turing model of computation. The precise computational complexity of SSR has been a notorious open problem ~\cite{ggj} over the last four decades. The problem is known to admit an upper bound in the third level of the Counting Hierarchy, i.e., $P^{PP^{PP^{PP}}}$ and no non-trivial lower bounds are known. Even when the input numbers are small, i.e., given in unary, no better complexity bound was known prior to our work. In this paper, we show that the unary variant (USSR) of the sum of square roots problem is considerably easier by giving a P/poly upper bound.