On the Hardness of Permanent
On the Hardness of Permanent
复制标题
关于永久硬度
DOI：
10.1007/3-540-49116-3_8
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
D. Sivakumar
中科院分区：
文献类型：
--
作者：
Jin;A. Pavan;D. Sivakumar
我们证明，如果存在一个多项式时间算法，可以计算所有输入的任意逆多项式分数的 n 阶矩阵的永久值，那么就存在一个 BPP 算法，可以计算每个矩阵的永久值。由此可见，该假设意味着 P #P = BPP。我们的算法适用于任何足够大的有限域（多项式大于假设成功率的倒数），或任何类似范围的整数区间。假设的算法也可以是概率多项式时间算法。我们的结果本质上是基于永久求解器的任何黑盒假设的最佳结果，并且是 Gemmell 和苏丹 [GS92]、Feige 和 Lund [FL92] 以及 Cai 和 Hemachandra [CH91] 和 Toda（参见 [ABG90]）结果的同时改进。
We prove that if there is a polynomial time algorithm which computes the permanent of a matrix of order n for any inverse polynomial fraction of all inputs, then there is a BPP algorithm computing the permanent for every matrix. It follows that this hypothesis implies P #P = BPP. Our algorithm works over any sufficiently large finite field (polynomially larger than the inverse of the assumed success ratio), or any interval of integers of similar range. The assumed algorithm can also be a probabilistic polynomial time algorithm. Our result is essentially the best possible based on any black box assumption of permanent solvers, and is a simultaneous improvement of the results of Gemmell and Sudan [GS92], Feige and Lund [FL92] as well as Cai and Hemachandra [CH91], and Toda (see [ABG90]).