Already ten years before the BSS-paper, Valiant (1979, 1982) had proposed an analogue of the theory of NP-completeness in an entirely algebraic framework, in connection with his famous hardness result for the permanent. While the part of his theory based on the Turing approach (#P-completeness) is now standard and well-known among the theoretical computer science community, his algebraic completeness result for the permanents received much less attention. The first account of Valiant's algebraic theory with elaborated proofs was von zur Gathen's survey (1987). A more recent treatment, with different proofs, can be found in the last chapter of our book (1996).
In this research monograph, we further develop Valiant's approach, and clarify its connections both to the discrete and to the BSS-model. We think this adds considerably to our understanding of the concept of completeness in algebraic models of computation.
Our book is organized as follows. The introduction overviews the three known theories of NP-completeness and explains our main results in an informal way. After a detailed treatment of Valiant's model in Chap. 2, we proceed in Chap. 3 by showing that the generating functions of various NP (or #P) complete graph properties are complete in Valiant's sense. The proofs are mainly based on graph theoretical constructions.
In Chap. 4, we relate Valiant's model to the classical discrete theory. Unexpectedly, parallel complexity classes enter. We rely on techniques from algebraic geometry and number theory, and our main result hinges on the generalized Riemann hypothesis. (These results will appear in TCS.)
The next chapter is devoted to investigations in the spirit of structural complexity. We prove that any countable poset can embedded in the poset of p-degrees, if Valiant's hypothesis is true. A striking result here is the discovery of a specific family of polynomials (cut enumerators), which is neither complete nor p-computable, provided the polynomial hierarchy does not collapse. (An extended abstract of these results appeared in Proc. STACS '98.)
In Chap. 6 we deviate a little from our main line of investigation. We develop a fast algorithm to evaluate irreducible rational matrix representations of complex general linear groups with respect to a symmetry adapted basis (Gelfand-Tsetlin basis). The connection to our main topic then becomes clear in the next chapter.
Immanants are matrix functions defined in terms of characters of the symmetric group, which generalize the permanent and determinant. For a deeper understanding of the amazingly different complexity behaviour of determinants and permanants, they are a natural object to study. Moreover, they give also an indication of the complexity to evaluate single entries of invariant matrices of general linear groups. Our algorithm of Chap. 6 yields upper complexity bounds for immanants, which improve previous bounds due to Hartmann (1985) and Barvinok (1990). The main efforts of Chap. 7 consist of proofs that the evaluation of immanants corresponding to certain hook diagrams or rectangular diagrams are complete in Valiant's sense. (An extended abstract of the results in Chap. 6 and 7 appeared in Proc. FPSAC '98, a full version is submitted.)
Finally, Chap. 8 contains some separation results and establishes a connection between Valiant's and the Blum-Shub-Smale model. We discuss possible directions for a deeper understanding of this connection.
Seventeen conjectures and open problems, distributed throughout the text, suggest further research. Some of them have resisted serious attempts for solution by the author.
I am grateful to the Institute for Applied Mathematics of the University of Zurich for making this research possible. In particular, I would like to thank Andrew Barbour and Peter Gabriel for their support. I am greatly indebted to Steve Smale for inviting me to the Liu Bie Ju Centre for Mathematical Sciences at the City University of Hong Kong, where this work was completed.
I am grateful to Fred and Lilly Haemmerli for their help in the final stage of this project. Finally, I wish to thank my wife Brigitte for her support, patience, and understanding, and to our little daughter Ladina for her cheerful presence.
Zurich, August 1998Peter Buergisser