Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Forschungspapier

On the Relative Power of Reduction Notions in Arithmetic Circuit Complexity

MPG-Autoren
/persons/resource/persons202366

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

Externe Ressourcen
Es sind keine externen Ressourcen hinterlegt
Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)

arXiv:1609.05942.pdf
(Preprint), 125KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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


Zitierlink: https://hdl.handle.net/11858/00-001M-0000-002C-4F8E-E
Zusammenfassung
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.