#####
Séminaire Lotharingien de Combinatoire, B36c (1996), 17pp.

# Michael Clausen

# Algebraische Komplexitätstheorie III:
Zur Berechnungskomplexität von Permanenten

**Abstract.**
One of the most important topics in structural complexity theory is the question,
whether nondeterministic polynomial time for Turing machine computations is more
powerful than deterministic polynomial time, i.e., whether **P** =!=
**NP**.
In this paper we survey a nonuniform algebraic analogue of the theory of
**NP**-completeness due to Valiant. We introduce the complexity classes
**VP** and
**VNP** consisting of *p*-computable and *p*-definable families of multivariate
polynomials, respectively. Typical members of **VP** and **VNP** are the families of
determinants and permanents of matrices with indeterminate entries over a fixed field
*k*. While determinants can be computed in polynomial time, all known algorithms for
the permanents need exponential time. A theoretical foundation of this surprising
difference is supplied by Valiant's theorem stating that the permanent family is
**VNP**-complete (over fields of characteristic different from two). We sketch a
simplified proof of this result and conclude our discussion with Valiant's extended
hypothesis which can be formulated in purely algebraic-combinatorial terms.

The following versions are available: