Efficient solving of combinatorial optimization problems is crucial in many areas of science. Unfortunately developing efficient algorithms for a large class (the NP-complete) of these problems is practically an impossible task. Yet problems from this class are encountered in many applications and the practically arising instances might, in fact, be easy to solve. It is thus crucial to understand in detail when an optimization problem is typically hard and what are the main reasons for this. Last decade witnessed a success in applying ideas from physics of disordered systems, spin glasses in particular, to combinatorial optimization problems. Methodologically a prominent role is played by the cavity method. It is beyond doubts that exploring the glassiness of these problems and related structural properties gives priceless insight about the origin of average algorithmic hardness. In this talk I will review our current understanding of which structural properties of combinatorial optimization problems have influence on their average computational complexity. After that I will show how ideas familiar to computer science (planting of solutions and reconstruction on trees) bring powerful generalization of the current methods and lead us to more complete description of the energy landscape. I will conclude by highlighting the range of applications of these generalizations to problems of physics, like jamming or structural glasses, and also address the problem of level crossings and temperature chaos.