Sparse Polynomial Divisibility Test over Finite Field is CoNP-hard

2026/06/10 by Yichuan Cao, Ruichen Qiu, Qiao-Long Huang +2 · 1 voice
Computer Science · #cs.SC #cs.CC

paper · pdf

Abstract

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.

Citations

• Fast polynomial computations with space constraints
• Sumsets, 3SUM, Subset Sum: Now for Real!
• Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
• A New Bound on Cofactors of Sparse Polynomials
• What Can (and Can't) we Do with Sparse Polynomials?
• Sub-Linear Root Detection, and New Hardness Results, for Sparse Polynomials Over Finite Fields

Discussions

• Yichuan Cao, Ruichen Qiu, Qiao-Long Huang, Ruyong Feng, Xiao-Shan Gao: Sparse Polynomial Divisibility Test over Finite Field is CoNP-hard https://arxiv.org/abs/2606.12130 https://arxiv.org/pdf/2606.12 [bsky, 0 points, 0 comments]

Related

• Output-sensitive Sparse Polynomial GCD over Finite Fields is NP-hard
• NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials
• Polynomial evaluation over finite fields: new algorithms and complexity bounds
• Computing sparse multiples of polynomials
• Sub-Linear Root Detection, and New Hardness Results, for Sparse Polynomials Over Finite Fields