USSR is in P/poly

2023/10/30 by Nikhil Balaji, Balaji, Nikhil, Samir Datta +1
Computer Science · Engineering · #Coding theory and cryptography #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #graph theory and CDMA systems #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2310.19335

openalex publication_date 2023/10/30 · openalex created_date 2023/11/02 · openalex updated_date 2026/07/28

Abstract

The Sum of Square Roots (SSR) problem is the following computational problem: Given positive integers a₁, …, a_k, and signs δ₁, …, δ_k ∈ \-1, 1\, check if ∑_i=1^k δ_i √(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 \citeggj over the last four decades. The problem is known to admit an upper bound in the third level of the Counting Hierarchy, i.e., \CHtwo 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.

Related

• On comparing sums of square roots of small integers
• Solving k-SUM using few linear queries
• An improved bound on sums of square roots via the subspace theorem
• Sums of square roots that are close to an integer
• PosSLP and Sum of Squares