The permanent and the determinant of a matrix are among the most important and most extensively studied polynomials in mathematics. Mathematical formulas for computing the permanent and the determinant have been studied since the 19th century. The smallest known mathematical formula for computing the permanent is of size exponential in the size of the underlying matrix, and the smallest known mathematical formula for computing the determinant is of size super-polynomial in the size of the underlying matrix. It is widely believed that for both the permanent and the determinant, there are no formulas of size polynomial in the size of the underlying matrix, but proving this conjecture is one of the most central open problems in theoretical computer science, and is related to the famous P versus NP question.
An interesting subclass of formulas is the class of multilinear formulas. A formula is called multilinear, if each of its sub-formulas computes a multilinear polynomial, that is, a polynomial of degree at most one in each of its input variables. Multilinear formulas are more intuitive as they do not allow the intermediate use of higher powers of variables, which finally cancel each other. Many of the known formulas for computing the permanent and the determinant are multilinear. In 2003, a Weizmann scientist proved that for both the permanent and the determinant, there are no multilinear formulas of size polynomial in the size of the underlying matrix.