Computational Complexity is a really fascinating area of research. One particular surprising fact that i learned years ago is the discrepancy between the computational effort to compute the determinant of a matrix and the permanent of a matrix. The determinant is defined as:
\begin{equation}
\text{det}(\text{A}) = \sum_{\sigma \in S_n}\text{sign}(\sigma)\prod^n_{i=1}a_{i,\sigma_i}
\end{equation} and the permanent is
\begin{equation}
\text{perm}(\text{A}) = \sum_{\sigma \in S_n}\prod^n_{i=1}a_{i,\sigma_i}
\end{equation} The difference in notation is minimal. The determinant considers the sign of the permutations $\sigma$ whereof the permanent does not. This little difference is responsible for the huge gap between the necessary resources that are needed in order to compute the actual value of these functions. The determinant can be evaluated in time that is polynomial in the dimension $n$, whereof the permanent is only computable in time that is exponential in $n$, e.g., using the $\mathcal{O}(n2^n)$ algorithm of Ryser. In the year 1979 Leslie Valiant [
1,
2] showed that the permanent is even #P-complete and he shows the same for any computation of $\text{perm}(\text{A}) \mod{p}$ for $p > 2$. To proof this, Valiant created a graph that encodes a boolean formula $f$. Due to his clever construction, the permanent of the graph's adjacency matrix is equal to the number of satisfying solution of the boolean formula $f$. It is a beutiful result and shows clearly that the computation of the permanent can probably not be done in an efficient way, i.e., polynomial in the matrix dimension. Note that if someone could compute the number of satisfying solutions of a formula $f$, such an algorithm can also be used to:
- Decide if a given formula $f$ satisfiable, i.e. to solve the $\text{SAT}$ problem
- If $f$ is satisfiable, to give a satisfying assignment of its variables. (Can be used to factorize integers)
