The purpose of this note is to study the relationship between a certain stability criterion for non-linear delay systems, obtained via the Lyapunov-Krasovskii method, and a delay-independent version of the small gain theorem. We show that, contrary to the delay-free case (in which the Kalman-Yakubovich-Popov lemma ensures the equivalence of the two approaches), the first method assumes stronger hypothesis than the second one. However, numerical verification of the former is in general NP-hard, whereas the latter leads to linear matrix inequalities. The difference between the two approaches is precisely stated, and, among other benefits, this permits to exhibit classes of problems for which the Lyapunov-Krasovskii method is not conservative.