Irreducibility Testing of Sparse Polynomials over Integers is NP-hard and Probabilistic Polynomial Time
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
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?