Tractable Depth Bounded Logics and the Problem of Logical Omniscience

In this paper we set out to make a contribution towards the solution of the logical omniscience problem. We maintain that the problem can be properly solved by restricting the classical notion of logical consequence rather than by waiving closure of the propositional attitudes under logical consequence. We suggest that an interesting alternative solution could be based on Depth-Bounded Boolean Logics, a novel incremental approach to the characterization of classical propositional logic that construes it as the limit of an infinite sequence of weaker tractable logics. Agents committed to these logics can be seen as approximations to the idealized reasoning agent of standard epistemic, doxastic and information logic. The full decision problem for each of the approximating logics is solvable in polynomial time - although its complexity grows as we proceed along the approximation sequence - with no restriction to any particular syntactic fragment. Moreover, the meaning of the logical operators is the same for al l logics and is explained in purely informational terms - that is, in terms of informational interpretations of " true" and "false" - in such a way that the most basic inference principles of classical propositional logic, including disjunctive syllogism, are preserved throughout the sequence.