The Problem
Standard logical systems model logically omniscient agents able to correctly recognize all consequences of their assumptions according to the system in use — and provide no sensible means to account for the cost of inferring them. In contrast, a resource-bounded agent cannot be expected to effectively perform all the correct inferences of a certain logic L, but only those that are within the reach of its limited resources.
A promising way out of this problem is through approximation. Given a logic L, we shall define a hierarchy of approximating logical systems that converge to L in such a way that these approximations satisfy minimal rational requirement and can be sensibly used as formal models of the deductive power of resource-bounded agents.
In this way, idealized logics are not dismissed as descriptively inadequate, but still play a crucial role as limiting normative theories to which approximating models should converge. At the same time, robust solutions to this problem are likely to have a significant practical impact in many research areas.
The Idea
We define a hierarchy of approximating logical systems converging to classical propositional logic. A natural measure of the difficulty of logical deduction can be obtained by focusing on the essential use of virtual information, as opposed to actual information, and on the depth at which this use is required to infer a given conclusion.
Actual Information
In this easy step, the sudoku rules dictate a certain alternative (i.e., number 2 is in the green cell) by excluding one by one all the others.
Virtual Information
By contrast, in this harder sudoku step, we essentially need to consider virtual information, i.e., potential extensions of the actual information state, and recognize that in all those potential extensions the content of the red cell is the same number (i.e., number 4).
Depth
It may be that, before the alternatives agree on the content of a cell, further case analysis is required involving further virtual information. The depth at which the nested use of virtual information is required provides an interesting and plausible measure of the difficulty of solving a puzzle.