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

Abstract

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