Counting Value Sets: Algorithm and Complexity

MaRDI QIDQ2949496zbMATH OpenFDO

Authors Qi Cheng, Joshua E. Hill, Daqing Wan

Publication date 1 October 2015

Full work available at URL https://arxiv.org/abs/1111.1224

zbMATH Keywords

finite fieldNP-hard, \#P-hardpoint countingpolynomial timepolynomial value set cardinalityrandomized polynomial timeRP-reductionsparse polynomialstraight-line programsubset sum problem

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Number-theoretic algorithms; complexity (11Y16) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: Let $p$ be a prime. Given a polynomial in $F_{p^m}[x]$ of degree $d$ over the finite field $F_{p^m}$, one can view it as a map from $F_{p^m}$ to $F_{p^m}$, and examine the image of this map, also known as the value set. In this paper, we present the first non-trivial algorithm and the first complexity result on computing the cardinality of this value set. We show an elementary connection between this cardinality and the number of points on a family of varieties in affine space. We then apply Lauder and Wan's $p$-adic point-counting algorithm to count these points, resulting in a non-trivial algorithm for calculating the cardinality of the value set. The running time of our algorithm is $(pmd{)}^{O(d)}$. In particular, this is a polynomial time algorithm for fixed $d$ if $p$ is reasonably small. We also show that the problem is #P-hard when the polynomial is given in a sparse representation, $p=2$, and $m$ is allowed to vary, or when the polynomial is given as a straight-line program, $m=1$ and $p$ is allowed to vary. Additionally, we prove that it is NP-hard to decide whether a polynomial represented by a straight-line program has a root in a prime-order finite field, thus resolving an open problem proposed by Kaltofen and Koiran in cite{Kaltofen03,KaltofenKo05}.

Recommendations

• scientific article; zbMATH DE number 1072530
• scientific article; zbMATH DE number 850077
• scientific article; zbMATH DE number 4064488
• Complexity dichotomy for counting problems
• Complexity dichotomies of counting problems
• Counting problems in parameterized complexity
• The complexity of counting problems
• scientific article; zbMATH DE number 2188478
• scientific article; zbMATH DE number 4072941

Cited in

(7)

• Moment subset sums over finite fields
• Sublinear root detection and new hardness results for sparse polynomials over finite fields
• Deep holes in Reed-Solomon codes based on Dickson polynomials
• Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants
• Finding and Counting MSTD Sets
• On complexity of searching for periods of functions given by polynomials over a prime field
• Value sets of non-permutation polynomials over the residue class rings of integers

This page was built for publication: Counting Value Sets: Algorithm and Complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2949496)