Computability in Europe 2006
Logical Approaches to Computational Barriers

Special Session Talk:
From a Zoo to a Zoology: Descriptive Complexity for Graph Polynomials

Speaker: Johann A. Makowsky


We outline a general theory of graph polynomials
which covers all the examples we found in the vast literature.
We introduce the class of (hyper)graph polynomials definable
in second order logic, and outline a research program
for their classification in terms of definability
and complexity comsiderations, and various notions of reducibilities. 

websites: Arnold Beckmann 2006-04-21