All reasoners described in the most widespread models of a rational reasoner exhibit logical omniscience, which is impossible for finite reasoners (real reasoners). The most common strategy for dealing with the problem of logical omniscience is to interpret the models using a notion of beliefs different from explicit beliefs. For example, the models could be interpreted as describing the beliefs that the reasoner would hold if the reasoner were able reason indefinitely (stable beliefs). Then the models would describe maximum rationality, (...) which a finite reasoner can only approach in the limit of a reasoning sequence. This strategy has important consequences for epistemology. If a finite reasoner can only approach maximum rationality in the limit of a reasoning sequence, then the efficiency of reasoning is epistemically (and not only pragmatically) relevant. In this paper, I present an argument to this conclusion and discuss its consequences, as, for example, the vindication of the principle 'no rationality through brute-force'. (shrink)

A Krom formula of pure quantification theory is a formula in conjunctive normal form such that each conjunct is a disjunction of at most two atomic formulas or negations of atomic formulas. Every class of Krom formulas that is determined by the form of their quantifier prefixes and which is known to have an unsolvable decision problem for satisfiability is here shown to be a conservative reduction class. Therefore both the general satisfiability problem, and the problem of satisfiability in finite (...) models, can be effectively reduced from arbitrary formulas to Krom formulas of these several prefix types. (shrink)