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: