On the Hardness of PosSLP

The problem 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 PosSLP remain unknown. In this paper, we demonstrate that PosSLP ∈ BPP would imply that NP ⊆ 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 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 PosSLP represents a significant advancement in understanding the complexity of this problem. It constitutes the first non-trivial lower bound for 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 #P-hard.