Holographic algorithms without matchgates

作     者：Landsberg, J. M. Morton, Jason Norine, Serguei 

作者机构：Texas A&M Univ Dept Math College Stn TX 77843 USA Penn State Univ Dept Math University Pk PA 16802 USA McGill Univ Dept Math & Stat Montreal PQ Canada 

出 版 物：《LINEAR ALGEBRA AND ITS APPLICATIONS》 (线性代数及其应用)

年 卷 期：2013年第438卷第2期

页      面：782-795页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：NSF [DMS-1006353, DMS-0803214] Defense Advanced Research Projects Agency [N66001-10-1-4040] Division Of Mathematical Sciences Direct For Mathematical & Physical Scien Funding Source: National Science Foundation 

主　　题：Holographic algorithms Pfaffian Spinors Matchgates 

摘      要：The theory of holographic algorithms, which are polynomial time algorithms for certain combinatorial counting problems, surprised the complexity community by showing certain problems, very similar to #P complete problems, were in fact in the class P. In particular, the theory produces algebraic tests for a problem to be in P. In this article we describe the geometric basis of these algorithms by (i) replacing the construction of graph fragments in the procedure by the direct construction of a skew symmetric matrix, and (ii) replacing the computation of weighted perfect matchings of an auxiliary graph by computing the Pfaffian of the directly constructed skew-symmetric matrix. This procedure indicates a more geometric approach to complexity classes. It also leads to more general constructions where one replaces the Grassmann-Pliicker identities which test for admissibility by other algebraic tests. Natural problems treatable by these methods have been previously considered in a different context, and we present one such example. (C) 2012 Elsevier Inc. All rights reserved.