Determinant versus permanent

  • Manindra Agrawal

    Indian Institute of Technology, Kanpur, India
Determinant versus permanent cover
Download Chapter PDF

A subscription is required to access this book chapter.

Abstract

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.