Skip to content
Preprint

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

Oct 2026 · 0 citations · 23 references
Computer Science

Abstract

In this paper, we prove that irreducibility testing for sparse polynomials in $\mathbb{Z}[X]$ is coNP-hard under deterministic polynomial-time many-one reductions. That is, there exists no polynomial-time irreducibility test algorithm unless $\mathrm P=\mathrm{NP}$. We also provide an upper bound for this problem by demonstrating that the same irreducibility testing problem lies in $\mathsf{PP}\subseteq\mathsf{PSPACE}$; in other words, it can be solved in probabilistic polynomial time and, moreover, within polynomial space. The fact that $\mathsf{SparseIrred}_{\mathbb{Z}}\in\mathsf{PP}$ 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.

View source

Similar papers

Preprint Oct 2026

Deterministic Shift Equivalence Testing for Sparse Polynomials

We study the shift equivalence testing problem for high-degree sparse multivariate polynomials. Given explicit spar se representations of two polynomials $f,g\in\mathbb{Q}[x_1,\ldots,x_n]$, with exponents encoded in binary, sparsities $s$ and $t$, and total degree at most $d$, the task is to decide whether there is a v...

M. Bläser, Pranjal Dutta, Sagnik Dutta et al. · 0 citations
Preprint Nov 2026

A Little Derandomization Goes a Long Way: Unconditional Circuit Lower Bounds using Low-Degree PIT

We prove unconditionally that either NE contains a language requiring Boolean circuits of size at least $2^n/(2n)$, or $VP^0_{\mathbb{Z}}\ne VNP^0_{\mathbb{Z}}$, a constant-free version of Valiant's conjecture over the integers. The Boolean alternative implies that $NP\not\subseteq SIZE[n^k]$ for every constant $k\ge1$...

Nikolai Chukhin, Karthik Gajulapalli, A. Golovnev et al. · 0 citations
Preprint Nov 2026

Deterministic Polynomial-Time Primality Testing with a Single Binomial Congruence

We give a deterministic polynomial-time primality test whose main verification is the congruence $(1+X)^n=1+X^n$ in $C_n[X]/(X^r-b(Y))$, where $C_n=(\mathbb{Z}/n\mathbb{Z})[Y]/(\Phi_r(Y))$. Two identities in the coefficient ring normalize $b$ and ensure compatibility with the main congruence. A finite-field root count...

Joseph M. Shunia · 0 citations
Preprint Nov 2026

$\mathsf{SVP}_\infty$ Is NP-Hard for Power-of-two Cyclotomic Ideals

We prove that exact decision-$\mathsf{SVP}$ in the coefficient $\ell_\infty$-norm is $\mathsf{NP}$-complete for principal ideals and free modules of rank two over the cyclotomic rings $R_n=\mathbb{Z}[X]/(X^n+1)$, where $n$ ranges over powers of two. For each case, we give a deterministic polynomial-time many-one reduct...

Yan-Song Feng, Jia-Qi Liu, Heng-Yi Luo et al. · 0 citations
Preprint Nov 2026

Reducible fibers of polynomials over integers: the Hilbert-Siegel problem over $\mathbb{Q}$ and its applications

Given a polynomial $f\in \mathbb{Q}[X]$, the Hilbert--Siegel problem asks for a description of the set of all values $t_0\in \mathbb{Z}$, possibly up to a finite set, such that $f(X)-t_0$ is reducible. Reducibility occurs trivially for $t_0$ in the value set of some non-linear left-composition factor of $f$. The proble...

J. König · 0 citations
Preprint Oct 2026

Unitary complexity in polynomial space

We show that if quantum commitments exist, then either there is no polynomial-time solution to the unitary synthesis problem, or $\mathsf{BPP} \neq \mathsf{NEXP}$. Thus, showing unconditionally that quantum commitments exist would require answering at least one of two longstanding open questions in complexity theory. W...

William Kretschmer, Ewin Tang · 1 citation

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.