Abstract In 1970, Jaakko Hintikka referred to the problem of accounting for the informativeness of deduction as the “scandal of deduction.”(Hintikka 1970) According to Hintikka, the problem seems to arise from the “tautological” or “analytical” nature of deduction: the conclusion validly deduced from a set of premises is said to be contained in that set. A straightforward way to understand this containment relation is to think that the information provided by the conclusion is already contained in the information provided by the premises. Under this assumption, it is problematic to explain how we can gain knowledge by deducing a logical consequence implied in a set of known premises, and because of this problem deduction has been considered uninformative and useless. To address this problem, we need an epistemological account to defend that knowledge can be gained through deduction, that is, an epistemological account to vindicate the usefulness and informativeness of deduction. The aim of this talk is to propose that the complexity of a decision problem known as Logical Entailment can lay the foundation for such an epistemological account.