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