It is already a consequence of the Cobham-Edmonds Thesis (together with the expected positive answers to Open Questions 1 and 2) that such problems are computationally intractable. But if we abandon the simplifying assumption that everyday reasoning is based on classical propositional logic, then validity and consistency checking only become harder. For instance, if we think that agents can reason about their own knowledge or that of others using a modal logic such as \(\mathsf{S4}\) or \(\mathsf{S5}_2\), then the corresponding validity and satisfiability problems become \(\textbf{PSPACE}\)-complete. And if we assume that they reason in propositional relevance logic, classical first-order logic, or intuitionistic first-order logic, then the validity problem becomes \(\textbf{RE}\)-complete (i.e. as hard as the Halting Problem).