Nature certainly poses a lot of hard problems to the physicist or the chemist.But can natural systems, or nature-inspired artifacts, be used to solve hard problems? This general question can be made a bit more precise by focusing on combinatorial optimization problems. Simple attempts at solving problems like Hamiltonian path or Steiner tree seem far from the goal, and in many case it seems that the occurence of a glassy transition, which freezes the relaxation in metastable states, is the major obstacle. Recently, some of the hardest constraint satisfaction problems have been addressed successfully through message passing methods, with algorithms which partly get around the freezing transition. The talk will review this approach and discuss its limitations. Message passing, which is a purely local strategy based on the exchange of simple probabilistic messages along a graph of constraints, is not only very powerful, but also appealing since its basic ingredients share some similarity with neural networks. This points to alternative, ``natural'' ways of solving hard problems, through artifacts which get around the basic physical limitations of usual thermal systems.