Irreducibility Testing of Sparse Polynomials over Integers is NP-hard and Probabilistic Polynomial Time

arXiv:2610.37179 · cs.CC · Submitted 2026-10-27 · Read on arXiv

cs.CC

Submitted: 2026-10-27

Updated: 2026-10-27

License: http://creativecommons.org/licenses/by/4.0/

The gist: In this paper, we prove that irreducibility testing for sparse polynomials in Z[X] is coNP-hard under deterministic polynomial-time many-one reductions.

Abstract

In this paper, we prove that irreducibility testing for sparse polynomials in Z[X] is coNP-hard under deterministic polynomial-time many-one reductions. That is, there exists no polynomial-time irreducibility test algorithm unless P= NP. We also provide an upper bound for this problem by demonstrating that the same irreducibility testing problem lies in; in other words, it can be solved in probabilistic polynomial time and, moreover, within polynomial space. The fact that Z in relies on the quasi-Riemann hypothesis result of Cureton--Thorner and on the uniform effective prime-ideal bound by Frei--Sofos--Widmer just posted recently.

Related papers