  We address the problem of quantifying the non-Markovian character of quantum
time-evolutions of general systems in contact with an environment. We introduce
two different measures of non-Markovianity that exploit the specific traits of
quantum correlations and are suitable for opposite experimental contexts. When
complete tomographic knowledge about the evolution is available, our measure
provides a necessary and sufficient condition to quantify strictly the
non-Markovianity. In the opposite case, when no information whatsoever is
available, we propose a sufficient condition for non-Markovianity. Remarkably,
no optimization procedure underlies our derivation, which greatly enhances the
practical relevance of the proposed criteria.
