# Item

ITEM ACTIONSEXPORT

Released

Paper

#### On the Relative Power of Reduction Notions in Arithmetic Circuit Complexity

##### Fulltext (public)

arXiv:1609.05942.pdf

(Preprint), 125KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Ikenmeyer, C., & Mengel, S. (2016). On the Relative Power of Reduction Notions in Arithmetic Circuit Complexity. Retrieved from http://arxiv.org/abs/1609.05942.

Cite as: http://hdl.handle.net/11858/00-001M-0000-002C-4F8E-E

##### Abstract

We show that the two main reduction notions in arithmetic circuit complexity,
p-projections and c-reductions, differ in power. We do so by showing
unconditionally that there are polynomials that are VNP-complete under
c-reductions but not under p-projections. We also show that the question of
which polynomials are VNP-complete under which type of reductions depends on
the underlying field.