Traditional logic is monotonic in the sense that if we deduce a statement \(Q\) from a theory \(T\), and then add a new statement \(S\) to this theory \(T\), then \(Q\) is still deducible from the extended theory \(T + \{S\}\). However, commonsense reasoning is often nonmonotonic: e.g., \(S\) may describe an exception to a general statement from the theory \(T\), in which case adding \(S\) to \(T\) may change the conclusion \(Q\) to \(\neg Q\). To describe such reasoning, several nonmonotonic formalisms have been proposed.
In the 1980s, McDermott and Doyle proposed a (reasonably general) method of generating such formalisms: as nonmonotonic versions of modal logics [D. McDermott and J. Doyle, Artif. Intell. 13, 41-72 (1980; Zbl 0435.68074); D. McDermott, J. Assoc. Comput. Mach. 29, 33-57 (1982; Zbl 0477.68099)]. The fact that this method is reasonably general was confirmed by G. Schwarz who showed in 1990 [R. Parikh (ed.), Proc. of TARK 1990, 97-109 (1990)] that autoepistemic logics, a widely used nonmonotonic formalism, can be reformulated in these terms.
The ultimate objective of nonmonotonic formalisms for representing uncertainty is to answer queries; therefore, the questions of computational complexity are extremely important. For all nonmonotonic modal logics for which computational complexity was analyzed before, this complexity coincided with the complexity of the corresponding monotonic modal logic (usually PSPACE). The authors show that for S4 nonmonotonic reasoning is simpler: namely, monotonic S4 is PSPACE-complete, while deducibility in nonmonotonic S4 is on the second level of the polynomial hierarchy (in \(\Sigma^P_2\) or in \(\Pi^P_2\)).
This result becomes somewhat less surprising when the authors show that for finite sets of formulas, a nonmonotonic version of S4 is equivalent to a nonmonotonic version of a slightly simpler modal logic S4F (whose complexity is in \(\Sigma^P_2\) or in \(\Pi^P_2\)).