de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Forschungspapier

On the Complexity of the Permanent in Various Computational Models

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons202366

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

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

arXiv:1610.00159.pdf
(Preprint), 217KB

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

Ikenmeyer, C., & Landsberg, J. M. (2016). On the Complexity of the Permanent in Various Computational Models. Retrieved from http://arxiv.org/abs/1610.00159.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-002C-4F1E-C
Zusammenfassung
We answer a question in [Landsberg, Ressayre, 2015], showing the regular determinantal complexity of the determinant det_m is O(m^3). We answer questions in, and generalize results of [Aravind, Joglekar, 2015], showing there is no rank one determinantal expression for perm_m or det_m when m >= 3. Finally we state and prove several "folklore" results relating different models of computation.