How does the spectral gap of a quantum many body system scale with the system size? This turns out to be a very relevant question both in condensed matter physics and in quantum computing. However, there are very few available techniques to give bounds of that scaling. In the first part of this talk, we will review recent results which explain why: it is undecidable to know if the spectral gap will vanish or not with the system size. In the second part, we will review complementary results which show that, despite this general impossibility result, one can still prove spectral gap estimates in a rather wide family of systems. As a consequence, one obtains new bounds on the lifetime of quantum memories.