#P- and oplusP- completeness of counting roots of a sparse polynomial
classification
💻 cs.CC
keywords
countingopluspolynomialrootssparsecompletenesscurvesdeterministic
read the original abstract
We improve and simplify the result of the part 4 of "Counting curves and their projections" (Joachim von zur Gathen, Marek Karpinski, Igor Shparlinski) by showing that counting roots of a sparse polynomial over $\mathbb{F}_{2^n}$ is #P- and $\oplus$P-complete under deterministic reductions.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.