Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR23-163 | 30th October 2023 11:46

USSR is in P/poly


Authors: Nikhil Balaji, Samir Datta
Publication: 2nd November 2023 03:44
Downloads: 126


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.

ISSN 1433-8092 | Imprint