The most direct links between complexity theory and epistemology which have thus far been discussed are mediated by the observation that deciding logical validity (and related properties) is generally a computationally difficult task. For on the one hand, a traditional view in epistemology is that logical knowledge – e.g. knowledge that certain statements are logical validities – is a paradigm case of a priori knowledge. If this is correct, then it would seem that we should credit normal epistemic agents with knowledge of the class of logically valid sentences of systems such as propositional and first-order logic which are commonly taken to underlie everyday reasoning. But on the other hand, the results presented in   Section 4.2  make clear that the problem of deciding whether \(\phi\) is a validity of one of these systems is computationally intractable.