Computability in Europe 2006
Logical Approaches to Computational Barriers
Special Session Talk:
|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|