This talk will consists of two distint but linked parts. Firstly I will review some key notions from statistical physics, such as 'phase transitions' and their connection to a variety of questions in computational complexity, including reconstruction problems on trees, and to the analysis of randomized algorithms. In the second part I will introduce a class of Monte Carlo Markov Chains which exihibit the phenomenon of "dynamical arrest", namely a dramatic increase of their mixing time when some parameter goes beyond a given threshold, without any counterpart at the level of their invariant measure. Besides their relevance to the description of glassy systems, some of these models may be of interest also to the theoretical computer science community.