This is the introductory chapter of the volume, which provides an overview of the interface between Statistical Physics and Computer Science: phase transitions, basic NP-complete problems, spin glasses, the replica formalism, rigorous results from Computer Science about phase transitions in combinatorial problems. A preliminary version is freely available from http://www.c3.lanl.gov/~percus/Research/LocalSearch/intro.pdf

The paper is not yet available online (it may become so in the future). The URL listed below is that of Real Analysis Exchange on Project Euclid.

For interval I and set A, denote by D(I,A) the class of functions from I to R such that: 1. range(f) = A. 2. for every x in A, f^{-1}(x) is dense in I. Motivated by a result due to Natkaniec and Kircheim (Real Analysis Exchange vol. 16 /1991-92) we show that D(I,A) is a subset of C+D, the class of functions that are the sum of a continuous and a Darboux function, if and only if set A is an interval. A preliminary version (called "On a paper by Natkaniec

Consider a system in which players at nodes of an underlying graph G repeatedly play Prisoner's Dilemma against their neighbors. The players adapt their strategies based on the past behavior of their opponents by applying the so-called win-stay lose-shift strategy. This dynamics has been studied by Shoham and Tennenholtz [1994], Kittock [1993], Dyer et al [2002], Mossel and Roch [2007]. Under random scheduling (i.e. when at each step the two nodes

Using recursive variants of Baire notions of nowhere dense and meagre sets we study the topological size of speedable and infinitely often speedable functions in a machine-independent framework. We show that the set of speedable functions is not ``small'' whereas the set of infinitely often speedable functions is ``large''. In this way we offer partial answers to a question in the first author's paper (C. Calude "Topological size of sets of partial

In analogy with the case of real functions we introduce and study the determining and stationary sets for some classes of unary p.r. functions, including the recursive and primitive recursive functions. As a by-product, a new characterization of Post simple sets is obtained.

We solve an open problem about the "self-reading sequences" considered in Paun and Salomaa (1993), namely we prove that all (nontrivial) such sequences contain every binary string.

We prove that all the self-reading sequences defined by Gh. Paun and A. Salomaa are not ultimately periodic, solving thus an open problem from that paper.

We define a version of structural equivalence of ET0L grammars, called strong equivalence, that takes into account their matrix structure, and prove its decidability.

Using a framework inspired by Schaefer's generalized satisfiability model [Sch78], Cohen, Cooper and Jeavons [CCJ94] studied the computational complexity of constraint satisfaction problems in the special case when the set of constraints is closed under permutation of labels and domain restriction, and precisely identified the tractable (and intractable) cases. Using the same model we characterize the complexity of three related problems: 1. counting