LOGICAL DEFINABILITY OF COUNTING FUNCTIONS

The relationship between counting functions and logical expressibility is explored. The most well studied class of counting functions is #P, which consists of the functions counting the accepting computation pa ths of a nondeterministic polynomial-time Turing machine. For a logic L, #L is the class of functions on finite structures counting the tupl es ((T) over bar, (c) over bar) satisfying a given formula psi((T) ove r bar, (c) over bar) in L. Saluja, Subrahmanyam, and Thakur showed tha t on classes of ordered structures #FO = #P (where FO denotes first-or der logic) and that every function in #Sigma(1) has a fully polynomial randomized approximation scheme. We give a probabilistic criterion fo r membership in #Sigma(1). A consequence is that functions counting th e number of cliques, the number of Hamilton cycles, and the number of pairs with distance greater than two in a graph, are not contained in #Sigma(1). It is shown that on ordered structures #Sigma(1)(1) capture s the previously studied class spanP. On unordered structures #FO is a proper subclass of #P and #Sigma(1)(1) is a proper subclass of spanP; in fact, no class #L contains all polynomial-time computable function s on unordered structures. However, it is shown that on unordered stru ctures every function in #P is identical almost everywhere with some f unction #FO, and similarly for #Sigma(1)(1) and spanP. Finally, we dis cuss the closure properties of #FO under arithmetic operations. (C) 19 96 Academic Press, Inc.