Holographic Algorithms on Domains of General Size

An essential problem in the design of holographic algorithms is to decide whether the required signatures can be realized by matchgates under a suitable basis transformation. For domain size two, Cai and Choudhary (2007, 2009) characterized all functions directly realizable as matchgate signatures without a basis transformation, and Cai and Lu (Theory Comput. Syst. 46(3), 398–415 2010; J. Comput. Syst. Sci. 77, 41–61 2011) gave a polynomial time algorithm for the realizability problem for symmetric signatures under basis transformations. We generalize this theory to arbitrary domain size k. Specifically, we give a polynomial time algorithm for the Simultaneous Realizability Problem on domain size k ≥ 3 for signatures realizable by matchgates over a basis of size 1. Using this, one can decide whether suitable signatures for a holographic algorithms on domain size k are realizable and if so, to find a suitable linear basis to realize these signatures by an efficient algorithm. We dedicate this paper to the memory of Alan L. Selman, a close personal friend and a former colleague of the second author, and also a former Editor-in-Chief for this journal. The results in this paper are a demonstration of the structure and unity of complexity theory. As this is a persistent theme of Professor Selman in his multifaceted and significant contributions to our field, we dedicate it to Alan as a tribute to his life and his influential work.