×

Holographic algorithms without matchgates. (English) Zbl 1257.05007

Summary: 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 \(\#{\mathbf P}\) complete problems, were in fact in the class \(\mathbf P\). In particular, the theory produces algebraic tests for a problem to be in \(\mathbf 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-Plücker 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.

MSC:

05A15 Exact enumeration problems, generating functions
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68W05 Nonnumerical algorithms
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
15B99 Special matrices
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Jin-Yi Cai, Vinay Choudhary, Some results on matchgates and holographic algorithms, in: Automata, Languages and Programming. Part I, Lecture Notes in Comput. Sci., vol. 4051, Springer, Berlin, 2006, pp. 703-714. · Zbl 1223.68120
[2] Jin-Yi Cai, Vinay Choudhary, Valiant’s holant theorem and matchgate tensors, in: Theory and Applications of Models of Computation, Lecture Notes in Comput. Sci., vol. 3959, Springer, Berlin, 2006, pp. 248-261. · Zbl 1178.68660
[3] Cai, Jin-Yi; Choudhary, Vinay, Valiant’s holant theorem and matchgate tensors, Theoret. Comput. Sci., 384, 1, 22-32 (2007) · Zbl 1124.68113
[4] Jin-Yi Cai, Pinyan Lu, Holographic algorithms: from art to science, in: STOC’07 - Proceedings of the 39th Annual ACM Symposium on Theory of Computing, ACM, New York, 2007, pp. 401-410. · Zbl 1232.68055
[5] Jin-Yi Cai, Pinyan Lu, Holographic algorithms: the power of dimensionality resolved, in: Automata Languages, and Programming, Lecture Notes in Comput. Sci., vol. 4596, Springer, Berlin, 2007, pp. 631-642. · Zbl 1171.68841
[6] Jin-Yi Cai, Pinyan Lu, On symmetric signatures in holographic algorithms, in: STACS 2007, Lecture Notes in Comput. Sci, vol. 4393, Springer, Berlin, 2007, pp. 429-440. · Zbl 1186.68540
[7] Cai, Jin-Yi; Lu, Pinyan, Basis collapse in holographic algorithms, Comput. Complexity, 17, 2, 254-281 (2008) · Zbl 1149.68036
[8] Jin-Yi Cai, Pinyan Lu, Mingji Xia, Holographic algorithms by fibonacci gates and holographic reductions for hardness, in: Proceedings of the 49th Annual Symposium on Foundations of Computer Science, 2008, pp. 644-653. · Zbl 1257.05004
[9] Claude Chevalley, The algebraic theory of spinors and Clifford algebras, Springer-Verlag, Berlin, 1997 (collected works, vol. 2, edited and with a foreword by Pierre Cartier and Catherine Chevalley, with a postface by J.-P. Bourguignon). · Zbl 0899.01032
[10] Chung, F. R.K.; Langlands, Robert P., A combinatorial Laplacian with vertex weights, J. Combin. Theory Ser. A, 75, 2, 316-327 (1996) · Zbl 0866.05039
[11] Hayes, B., Accidental algorithms, Amer. Scientist, 96, 1, 9-13 (2008)
[12] Ishikawa, Masao; Wakayama, Masato, Applications of minor-summation formula. II. Pfaffians and Schur polynomials, J. Combin. Theory Ser. A, 88, 1, 136-157 (1999) · Zbl 0947.15008
[13] Jaeger, F.; Vertigan, D. L.; Welsh, D. J.A., On the computational complexity of the Jones and Tutte polynomials, Math. Proc. Cambridge Philos. Soc., 108, 1, 35-53 (1990) · Zbl 0747.57006
[14] Kasteleyn, P. W., Graph Theory and Crystal Physics, Graph Theory and Theoretical Physics (1967), Academic Press: Academic Press London · Zbl 0205.28402
[15] Jason Morton, Pfaffian circuits, Preprint, arXiv:1101.0129.
[16] Norine, Serguei, Pfaffian graphs, T-joins and crossing numbers, Combinatorica, 28, 1, 89-98 (2008) · Zbl 1199.05075
[17] Stembridge, John R., Nonintersecting paths, Pfaffians, and plane partitions, Adv. Math., 83, 1, 96-131 (1990) · Zbl 0790.05007
[18] Temperley, H. N.V.; Fisher, Michael E., Dimer problem in statistical mechanics – an exact result, Philos. Mag., 8, 1061-1063 (1961) · Zbl 0126.25102
[19] Leslie G. Valiant, Quantum computers that can be simulated classically in polynomial time, in: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, ACM, New York, 2001, pp. 114-123 (electronic). · Zbl 1323.68283
[20] Valiant, Leslie G., Expressiveness of matchgates, Theoret. Comput. Sci., 289, 1, 457-471 (2002) · Zbl 1051.68064
[21] Valiant, Leslie G., Quantum circuits that can be simulated classically in polynomial time, SIAM J. Comput., 31, 4, 1229-1254 (2002) · Zbl 0997.81022
[22] Leslie G. Valiant, Accidental algorithms, in: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science 2006, 2004, pp. 509-517.
[23] Leslie G. Valiant, Holographic algorithms (extended abstract), in: Proceedings of the 45th annual Symposium on Foundations of Computer Science, 2004, pp. 306-315.
[24] Leslie G. Valiant, Holographic circuits, in: Automata, Languages and Programming, Lecture Notes in Comput. Sci., vol. 3580, Springer, Berlin, 2005, pp. 1-15. · Zbl 1081.68022
[25] Valiant, Leslie G., Holographic algorithms, SIAM J. Comput., 37, 5, 1565-1594 (2008) · Zbl 1152.05010
[26] Valiant, Leslie G.; Vazirani, V. V., NP is as easy as detecting unique solutions, Theoret. Comput. Sci., 47, 85-93 (1986) · Zbl 0621.68030
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.