Signature Theory in Holographic Algorithms

摘要

In the theory of holographic algorithms proposed by Valiant, computation is expressed and processed in terms of signatures. We substantially develop the signature theory in holographic algorithms. This theory is developed in terms of d-realizability and d-admissibility. For the class of 2-realizable signatures we prove a Birkhoff-type theorem which determines this class. It gives a complete structural understanding of the relationship between 2-realizability and 2-admissibility. This is followed by characterization theorems for 1-realizability and 1-admissibility. Finally, using this theory of general (i.e., unsymmetric) signatures we give additional counting problems solvable in polynomial time by holographic algorithms.