#P- and $\oplus$ P- completeness of counting roots of a sparse polynomial

preprint2016arXivOpen access

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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Write a reviewWrite

No reviews yet.

Add a commentWrite

No comments yet.

#P- and $\oplus$ P- completeness of counting roots of a sparse polynomial

Abstract

Connections

Building this map preview

Reviews 0

Discussion 0

#P- and ⊕\oplus⊕P- completeness of counting roots of a sparse polynomial

Abstract

Connections

Building this map preview

Reviews 0

Discussion 0

#P- and $\oplus$ P- completeness of counting roots of a sparse polynomial