##
Generalized Chromatic Polynomials and the Counting Complexity for Metafinite Structures

###
Janos Makowsky and Elena Ravve

We argue that metafinite model theory is the natural framework to study numeric graph parameters
and graph polynomials. However, from a complexity point of view, it is not clear how to measure the complexity
of computing numeric graph parameters or evaluating graph polynomials. The class $\sharp P_{\mathbb{R}}$aover the real numbers
introduced by K. Meer captures many, but not all examples studied in the literature.
Furthermore, the examples which are $\sharp P$-complete in the Turing model, such as the chromatic polynomial
evaluated on natural number greater or equal to 3, are unlikely to be $\sharp P_{\mathbb{R}}$-complete
in metafinite model theory, respectively in the Blum-Shub-Smale model of computation.
It turns out that the analogue class over the complex numbers is slightly better understood than its real counterpart.
We will discuss our attempts to define an analogue to Kalmar's elmentary functions in the BSS-model
and discuss many open problems arising from this approach.

Based on joint work with T. Kotek