Holographic Algorithms and Reductions

全息算法的理论由可实现签名的性质来表示。由Les Valiant发起的新算法设计原则使用这些签名来找到解决各种计数问题的高效和非常规算法。我们已经发展了对称签名的实质性理论，这是特别有用的，因为它们具有明确的组合意义。然而，为了理解全息算法的全部功能，我们必须理解可实现的但不对称的签名。非对称签名的理论要复杂得多。基于匹配门和Pfaffians，我们提出了一个完整的非对称签名分类定理，特别是在计算复杂性理论中，这项研究的目的是从根本上理解高效计算的本质。全息算法挑战了我们关于什么是有效计算的概念。这项研究将明确什么是可计算的，什么是不能有效计算的。所开发的证明技术也可能广泛适用于复杂性理论的相关领域。所有可实现签名(包括对称签名和非对称签名)的分类定理将有助于理解这些非传统全息算法的最终能力是什么。

The theory of holographic algorithms is expressed by the properties of realizable signatures. The new algorithmic design principles initiated by Les Valiant use these signatures to find efficient and unconventional algorithms for a variety of counting problems. We have already developed a substantial theory of symmetric signatures, which are particularly useful since they have clear combinatorial meanings. However in order to understand the full power of holographic algorithms we must understand realizable but unsymmetric signatures. The theory of unsymmetric signatures is substantially more involved. We propose to work toward a complete classification theorem of unsymmetric signatures based on matchgates and Pfaffians.The goal of this research in particular, and in computational complexity theory in general, is to gain a fundamental understanding of the nature of efficient computation. Holographic algorithms challenge our conception of what is efficiently computable. This study will sharpen the boundary of what is and what is not efficiently computable. The proof techniques developed may also be broadly applicable in related areas of complexity theory. The classification theorem for all realizable signatures (including symmetric as well as unsymmetric signatures) will go a long way toward an understanding of what the ultimate capabilities are with these unconventional holographic algorithms.