2023/07/16 by Peter Bürgisser, Bürgisser, Peter, Gorav Jindal +1
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Formal Methods in Verification #Numerical Analysis (math.NA) #Numerical Methods and Algorithms #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.2307.08008
openalex publication_date 2023/07/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The problem \textrmPosSLP involves determining whether an integer computed by a given straight-line program is positive. This problem has attracted considerable attention within the field of computational complexity as it provides a complete characterization of the complexity associated with numerical computation. However, non-trivial lower bounds for \textrmPosSLP remain unknown. In this paper, we demonstrate that \textrmPosSLP ∈ \textrmBPP would imply that \textrmNP ⊆ \textrmBPP, under the assumption of a conjecture concerning the complexity of the radical of a polynomial proposed by Dutta, Saxena, and Sinhababu (STOC'2018). Our proof builds upon the established \textrmNP-hardness of determining if a univariate polynomial computed by an SLP has a real root, as demonstrated by Perrucci and Sabia (JDA'2005). Therefore, our lower bound for \textrmPosSLP represents a significant advancement in understanding the complexity of this problem. It constitutes the first non-trivial lower bound for \textrmPosSLP , albeit conditionally. Additionally, we show that counting the real roots of an integer univariate polynomial, given as input by a straight-line program, is #\textrmP-hard.