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.