Negation can be exponentially powerful
Negation can be exponentially powerful
复制标题
否定的力量可以呈指数级增长
DOI：
10.1145/800135.804412
复制
发表时间：
1979
期刊：
影响因子：
--
通讯作者：
L. Valiant
中科院分区：
文献类型：
--
作者：
L. Valiant
在代数中，最引人注目的算法是STRASSEN的算法，用于繁殖的算法，对于这两种问题的卷积，快速的傅立叶变换方法。 18]表明，这些算法分别使用＆thgr;（n3）和＆thgr;（n2）操作，在仅使用这些单调的算法中实质上是最佳的通过使用减法作为额外的操作和以非常复杂的方式利用计算术语的操作。以类似的方式，我们是否可以通过这种明智的取消使用来期望我们的计算效率提高。答案是，通过展示一个问题，可以使用{+， - ，×}附加指数加速，而不仅仅是{+，×}作为操作。为此，快速的算法是Fisher和Kasteleyn的PFAFFIAN技术[6,8]。
Among the most remarkable algorithms in algebra are Strassen's algorithm for the multiplication of matrices and the Fast Fourier Transform method for the convolution of vectors. For both of these problems the definition suggests an obvious algorithm that uses just the monotone operations + and ×. Schnorr [18] has shown that these algorithms, which use &thgr;(n3) and &THgr;(n2) operations respectively, are essentially optimal among algorithms that use only these monotone operations. By using subtraction as an additional operation and exploiting cancellations of computed terms in a very intricate way Strassen showed that a faster algorithm requiring only O(n2.81) operations is possible. The FFT method for convolution achieves O(nlog n) complexity in a similar fashion. The question arises as to whether we can expect even greater gains in computational efficiency by such judicious use of cancellations. In this paper we give a positive answer to this, by exhibiting a problem for which an exponential speedup can be attained using {+,−,×} rather than just {+,×} as operations. The problem in question is the multivariate polynomial associated with perfect matchings in planar graphs. For this a fast algorithm is implicit in the Pfaffian technique of Fisher and Kasteleyn [6,8]. The main result we provide here is the exponential lower bound in the monotone case.