@article{COMPTON1996283,
    Abstract = {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 paths of a nondeterministic polynomial-time Turing machine. For a logicL, \#Lis the class of functions on finite structures counting the tuples (T, ) satisfying a given formulaψ(T, ) inL. Saluja, Subrahmanyam, and Thakur showed that on classes of ordered structures \#FO=\#P (where FO denotes first-order logic) and that every function in \#Σ1has a fully polynomial randomized approximation scheme. We give a probabilistic criterion for membership in \#Σ1. A consequence is that functions counting the 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 \#Σ1. It is shown that on ordered structures \#Σ11captures the previously studied class spanP. On unordered structures \#FO is a proper subclass of \#P and \#Σ11is a proper subclass of spanP; in fact, no class \#Lcontains all polynomial-time computable functions on unordered structures. However, it is shown that on unordered structures every function in \#P is identical almost everywhere with some function \#FO, and similarly for \#Sgr;11and spanP. Finally, we discuss the closure properties of \#FO under arithmetical operations.},
    Author = {Compton, Kevin J. and Gr{\"a}del, Erich},
    File = {Logical Definability of Counting Functions - 1-s2.0-S0022000096900690-main.pdf},
    ISSN = {0022-0000},
    Journal = {Journal of Computer and System Sciences},
    Number = {2},
    Pages = {283-297},
    Title = {Logical Definability of Counting Functions},
    URL = {https://www.sciencedirect.com/science/article/pii/S0022000096900690},
    Volume = {53},
    Year = {1996},
    bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/S0022000096900690},
    bdsk-url-2 = {https://doi.org/10.1006/jcss.1996.0069},
    date-added = {2022-07-16 09:03:06 +0200},
    date-modified = {2022-07-16 09:03:06 +0200},
    doi = {10.1006/jcss.1996.0069}
}

@article{COMPTON1996283, Abstract = {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 paths of a nondeterministic polynomial-time Turing machine. For a logicL, #Lis the class of functions on finite structures counting the tuples (T, ) satisfying a given formulaψ(T, ) inL. Saluja, Subrahmanyam, and Thakur showed that on classes of ordered structures #FO=#P (where FO denotes first-order logic) and that every function in #Σ1has a fully polynomial randomized approximation scheme. We give a probabilistic criterion for membership in #Σ1. A consequence is that functions counting the 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 #Σ1. It is shown that on ordered structures #Σ11captures the previously studied class spanP. On unordered structures #FO is a proper subclass of #P and #Σ11is a proper subclass of spanP; in fact, no class #Lcontains all polynomial-time computable functions on unordered structures. However, it is shown that on unordered structures every function in #P is identical almost everywhere with some function #FO, and similarly for #Sgr;11and spanP. Finally, we discuss the closure properties of #FO under arithmetical operations.}, Author = {Compton, Kevin J. and Gr{\"a}del, Erich}, File = {Logical Definability of Counting Functions - 1-s2.0-S0022000096900690-main.pdf}, ISSN = {0022-0000}, Journal = {Journal of Computer and System Sciences}, Number = {2}, Pages = {283-297}, Title = {Logical Definability of Counting Functions}, URL = {https://www.sciencedirect.com/science/article/pii/S0022000096900690}, Volume = {53}, Year = {1996}, bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/S0022000096900690}, bdsk-url-2 = {https://doi.org/10.1006/jcss.1996.0069}, date-added = {2022-07-16 09:03:06 +0200}, date-modified = {2022-07-16 09:03:06 +0200}, doi = {10.1006/jcss.1996.0069} }