Feasible arithmetic computations: Valiant's hypothesis (Q1114391)

This paper gives an introduction to complexity classes of polynomials over a field. The basic notion is a straight-line program over a field F. Such a program does not contain loops. It consists of steps which are either additions, subtractions, multiplications or divisions over F, with results of earlier lines, or an input of an element of F. Such algorithms give rise to complexity classes of polynomials that are called p- computable, p-expressible, qp-computable, qp-expressible or p-definable. The definitions of these classes are too complex to put them here. It is proven that p-expressible implies p-computable implies p-definable. Moreover it can be shown that p-computable does not imply p-expressible. Vaillant's hypothesis conjectures that p-definable is not equal to p- computable. This is a polynomial variant of the \(P\neq NP\) conjecture. A p-complete family of polynomials is a family that is the computational hardest in the class p-definable. It is shown that the permanent family, i.e., \(f_ n\) computes the general permanent of an \(n\times n\)-matrix, is p-complete.