Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic |
| |
Authors: | Jin-Yi Cai Xi Chen Dong Li |
| |
Affiliation: | 1. Computer Sciences Department, University of Wisconsin-Madison, Madison, WI, 53706-1685, USA 2. Department of Computer Science, Princeton University, Princeton, NJ, 08540-5233, USA 3. School of Mathematics, Institute for Advanced Study, Princeton, NJ, 08540, USA
|
| |
Abstract: | In Valiant’s theory of arithmetic complexity, the classes VP and VNP are analogs of P and NP. A fundamental problem concerning
these classes is the Permanent and Determinant Problem: Given a field
\mathbbF{\mathbb{F}} of characteristic ≠ 2, and an integer n, what is the minimum m such that the permanent of an n × n matrix X = (xij) can be expressed as a determinant of an m × m matrix, where the entries of the determinant matrix are affine linear functions of xij ’s, and the equality is in
\mathbbFX]{\mathbb{F}}{\bf X}]. Mignon and Ressayre (2004) proved a quadratic lower bound m = W(n2)m = \Omega(n^{2}) for fields of characteristic 0. We extend the Mignon–Ressayre quadratic lower bound to all fields of characteristic ≠ 2. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|