Computing Permanents over Fields of Characteristic 3:
Where and Why it Becomes Difficult

G. Kogan and J.A. Makowsky

Department of Computer Science
Technion - Israel Institute of Technology
Haifa, Israel
{grishak,janos\}@@cs.technion.ac.il
December, 1997

In this paper we consider the complexity of computing permanents over fields of characteristic 3. We present a polynomial time algorithm for computing $\Per (A)$ for a matrix $A$ such that $\rank (AA^T - I) \leq 1$. On the other hand, we show that existence of a polynomial-time algorithm for computing $\Per (A)$ for a matrix $A$ such that $\rank (AA^T - I) \geq 2$ implies $\bnp = \br$. As a byproduct we obtain that computing $\Per (A)$ for a matrix $A$ such that $\rank (AA^T - I) \geq 2$ is $Mod_3\bP $-complete.