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

Michael Clausen

Séminaire lotharingien de combinatoire, Tome 36 (1996)

Résumé

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.