de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

On the Relative Power of Reduction Notions in Arithmetic Circuit Complexity

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons202366

Ikenmeyer,  Christian
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
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.