Permanent vs determinant

[Stas Busygin]

Permanent vs determinant is the arithmetic version of NC vs #P problem
that is primarily addressed in Mulmuley's work. A useful survey on the
problem can be found here:

http://www.cse.iitk.ac.in/users/manindra/survey/Determinant.pdf

So, we consider a matrix X={x_{ij}}_{n \times n} and ask if perm(X)
can be expressed linearly as determinant of a (possibly larger but
polynomial in size) matrix Y={y_{kl}}_{m \times m}:

y_{kl} = \sum_i \sum_j a_{kl}^{ij} x_{ij} + a_{kl}^{00} (1)

A naive approach would be to generate enough matrices X1, X2, ..., XN
to consider the system of polynomial equations in a's:

perm(Xp)=det(Yp), p=1...N

and decide that Y is not big enough if it doesn't have a solution.
Though it is unlikely that we can use this approach having n as a
parameter going to infinity, we already know that Mulmuley's so-called
"weak" NC vs #P result is provable with an extremely simple one-page
argument:

http://www.math.princeton.edu/~balexeev/weak.pdf

So, having simple satisfiability criteria for polynomial equations in
mind wouldn't hurt...