The problem $\textrm{ PosSLP}$ 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 $\textrm{ PosSLP}$ remain unknown. In this paper, we demonstrate that $\textrm{ PosSLP} \in \textrm{ BPP}$ would imply that $\textrm{ NP} \subseteq \textrm{ BPP}$, 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 $\textrm{ NP}$-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 $\textrm{ PosSLP}$ represents a significant advancement in understanding the complexity of this problem. It constitutes the first non-trivial lower bound for $\textrm{ PosSLP}$ , albeit conditionally. Additionally, we show that counting the real roots of an integer univariate polynomial, given as input by a straight-line program, is $\#\textrm{ P}$-hard.

Categories: cs.CC cs.NA math.NA

On the Hardness of PosSLP