Computing permanents over fields of characteristic 3: where and why it becomes difficult
Grigoriy P. Kogan · 2002
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 the rank rg(AA/sup T/-I)/spl les/1. On the other hand, we show that existence of a polynomial-time algorithm for computing per(A) for a matrix A such that rg(AA/sup T/-I)/spl ges/2 implies NP=R. As a byproduct we obtain that computing per(A) for a matrix A such that rg(AA/sup T/-I)/spl ges/2 is P(mod3) complete.