Sparse Polynomial Divisibility Test over Finite Field is CoNP-hard
For theoretical computer scientists, it establishes the exact complexity of a fundamental problem about sparse polynomials, showing it is likely intractable.
The paper proves that testing whether a sparse polynomial divides another over finite fields is CoNP-hard, resolving a long-standing open problem in computational complexity.
In this paper, we show that deciding whether a sparse polynomial does not divide another sparse polynomial exactly over finite fields is NP-hard under BPP many-one reductions. Equivalently, the sparse polynomial divisibility test over finite fields is CoNP-hard. This resolves the long-standing open problem concerning the computational complexity of the divisibility test for sparse polynomials in the setting of finite fields.