VIsualIzatIon by Jared tarbell
class of functions,b like the number of
satisfying assignments of a Boolean
formula, that count the number of
solutions of the problems in NP, and
NC denotes the class of functions,b
like the determinant, that can be computed efficiently in parallel in polylogarithmic time using polynomially many
processors. The implication of the
permanent vs. determinant conjecture
from the (nonuniform) P vs. NC conjecture is based on the fact that the permanent is P-complete29 (in the spirit
b This definition of NC is broader than the usual
definition that allows only 0– 1 functions.
of the well-known NP-completeness)
and that the determinant is (almost)
NC-complete. It is also known that the
permanent vs. determinant conjec-
ture, when K is a large enough finite
field Fp and m = O(2clog2n) for some
large enough constant c > 0, implies
the P NC conjecture. As such, the
permanent vs. determinant conjecture
is, strictly speaking, an algebraic ana-
logue of the P vs. NC conjecture, not
the P vs. NP conjecture. There is also
an analogous algebraic analogue of the
P vs. NP conjecture21, 25 which, when K is
a large enough finite field, implies the
usual P ≠ NP conjecture. But its story
is similar to that of the permanent vs.
determinant conjecture. Hence, for
simplicity, we only focus on the perma-
nent vs. determinant conjecture here.