Determinant versus permanent

Autores: Manindra Agrawal
Localización: Proceedings oh the International Congress of Mathematicians: Madrid, August 22-30,2006 : invited lectures / coord. por Marta Sanz Solé , Javier Soria de Diego , Juan Luis Varona Malumbres , Joan Verdera , Vol. 3, 2006, ISBN 978-3-03719-022-7, págs. 985-998
Idioma: inglés
Enlaces
- Texto completo (pdf)
Resumen
- We study the problem of expressing permanents of matrices as determinants of (possibly larger) matrices. This problem has close connections to the complexity of arithmetic computations: the complexities of computing permanent and determinant roughly correspond to arithmetic versions of the classes NP and P respectively. We survey known results about their relative complexity and describe two recently developed approaches that might lead to a proof of the conjecture that the permanent can only be expressed as the determinant of exponential-sized matrices.