Feasible arithmetic computations: Valiant's hypothesis

Polynomials in general fields (irreducibility, etc.) (12E05) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Review text

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.

Recommendations

Cites work

Cited in

(26)

This page was built for publication: Feasible arithmetic computations: Valiant's hypothesis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1114391)