This book constitutes the refereed proceedings of the 4th International Conference on Theory and Applications of Models of Computation, TAMC 2007, held in Shanghai, China in May 2007. It addresses all major areas in computer science; mathematics, especially logic; and the physical sciences, particularly with regard to computation and computability theory. The papers particularly focus on algorithms, complexity and computability theory.

This book constitutes the refereed proceedings of the Third International Conference on Theory and Applications of Models of Computation, TAMC 2006, held in Beijing, China, in May 2006. The 75 revised full papers presented together with 7 plenary talks were carefully reviewed and selected from 319 submissions. All major areas in computer science, mathematics (especially logic) and the physical sciences particularly with regard to computation and computability theory are addressed.

Complexity theory aims to understand and classify computational problems, especially decision problems, according to their inherent complexity. This book uses new techniques to expand the theory for use with counting problems. The authors present dichotomy classifications for broad classes of counting problems in the realm of P and NP. Classifications are proved for partition functions of spin systems, graph homomorphisms, constraint satisfaction problems, and Holant problems. The book assumes minimal prior knowledge of computational complexity theory, developing proof techniques as needed...