权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Holographic Algorithms and Reductions

全息算法和简化

基本信息

批准号：
0830488
负责人：
Jin-Yi Cai
金额：
$ 10万
依托单位：
University of Wisconsin-Madison
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2008
资助国家：
美国
起止时间：
2008-08-01 至 2011-07-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=0830488&HistoricalAwards=false
关键词：
Holographic Algorithms Reductions

项目摘要

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.

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