Reproduce “Irreducibility Testing of Sparse Polynomials over Integers is NP-hard and Probabilistic Polynomial Time” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Yichuan Cao, Xiao-Shan Gao, Qiao-Long Huang, Jiawei Nie
The authors show that deciding irreducibility of a univariate integer polynomial given by sparse coefficient–exponent pairs is coNP-hard under deterministic polynomial-time many-one reductions, and belongs to PP, hence PSPACE. Their reduction encodes satisfiability so that 3-UNSAT yields irreducible instances and 3-SAT reducible ones. The PP upper bound relies on external analytic results and primality testing; input size charges only exponent logarithms.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.