Classical logic is strictly monotonic: once a conclusion is proven true, it remains true forever, regardless of what new facts are added to the knowledge base. This allows reasoning engines to operate incrementally, accumulating truths like bricks in a wall. However, human common sense requires the ability to make default assumptions that can be overridden by new evidence—such as assuming a bird can fly until learning it is a penguin.
While this capacity for nonmonotonic reasoning is essential for realistic AI, it introduces a severe computational penalty. In a monotonic system, verifying a statement requires finding a single valid chain of deduction. In a nonmonotonic system, you must ensure that your conclusion is not invalidated by any other rule or exception in the entire knowledge base. This shift from local deduction to global consistency checking causes a dramatic complexity explosion.
The Extension Explosion and the Polynomial Hierarchy
To understand why nonmonotonic reasoning is hard, consider how frameworks like Reiter's Default Logic or Answer Set Programming (ASP) operate. Instead of a single set of true facts, these systems generate one or more extensions (or stable models)—globally consistent sets of beliefs that satisfy all default rules.
As shown by Artur Mikitiuk et al. in Constrained and Rational Default Logics, determining whether a specific formula belongs to a valid extension sits at the second level of the polynomial hierarchy ($\Sigma_2^p$ or $\Pi_2^p$-complete). This makes it significantly more difficult than standard NP-complete problems like Boolean satisfiability (SAT).
The reason for this jump lies in the "guess and verify" nature of the problem. In a standard NP problem, you guess a candidate solution and verify it in polynomial time. In default logic, however, verifying a guessed extension is not a polynomial-time task. To verify that a default rule was correctly applied, you must prove that its justification is consistent with the rest of the extension. Proving consistency requires showing that the negation of the justification cannot be derived—which is itself an entire coNP-hard subproblem. This nested structure—guessing an extension and then solving a coNP problem to verify it—drives the complexity up to the second level of the hierarchy, as detailed by Ilkka Niemelä in Towards Efficient Default Reasoning.
Predicate Minimization and Circumscription
Another prominent approach to nonmonotonic reasoning is John McCarthy's circumscription, which formalizes default assumptions by minimizing the extensions of specific predicates. For example, to reason that birds fly by default, the system minimizes an Abnormal predicate, effectively forcing it to assume everything is normal unless proven otherwise.
However, minimizing predicates introduces a severe computational overhead. As Eunok Paek notes in A Circumscriptive Theory for Causal and Evidential Support, calculating these minimal predicates is frequently NP-hard or worse. The intuition behind this difficulty lies in the definition of minimality: to prove that a model is minimal, you must show that there is no other valid model that contains a strictly smaller set of abnormal entities. This requires an exhaustive, global comparison across the space of possible models.
When circumscription is integrated into structured knowledge bases like Description Logics (DLs), the data complexity of evaluating queries shifts from polynomial time to $\Pi_2^p$-completeness. In Querying Circumscribed Description Logic Knowledge Bases, Quentin Manière et al. demonstrate that this computational tax is paid heavily as the volume of facts increases. The system must continuously verify that no alternative, more minimal configuration of exceptions exists for the dataset.
The Fragility of Lightweight Logics
A common strategy in knowledge representation is to use "lightweight" logics—such as the description logic $\mathcal{EL}^{++}$ or DL-Lite—which deliberately restrict expressivity to guarantee polynomial-time ($P$) reasoning. One might hope that adding default rules to an already efficient base logic would yield a manageable complexity increase.
Unfortunately, nonmonotonicity destroys this tractability. Umberto Straccia demonstrates in Default Inheritance Reasoning in Hybrid KL-ONE-Style Logics that integrating default inheritance into otherwise tractable description logics immediately drives the complexity up to NP-hard. Similarly, Piero A. Bonatti et al. show in Adding Default Attributes to EL++ that combining non-monotonic defaults with features like role compositions triggers a transition to coNP-hard complexity.
The core reason for this breakdown is that default rules introduce implicit disjunction. Saying "a bird flies unless it is abnormal" splits the reasoning path into two distinct possibilities for every single bird: either the bird is normal and flies, or it is abnormal and does not. This reintroduces the exact type of combinatorial, branch-heavy reasoning that lightweight logics were specifically designed to avoid, turning a linear scan of facts into an exponential search space.
Taming the Complexity
Given these steep theoretical barriers, researchers focus on identifying structural "backdoors" or restricted fragments where the worst-case complexity can be avoided. For instance, Johannes Klaus Fichte explores this in Backdoors to Tractability of Answer-Set Programming, showing that the combinatorial explosion can sometimes be confined to a small, isolated subset of variables, allowing the rest of the program to be solved efficiently. Understanding exactly why nonmonotonicity triggers these complexity jumps allows computer scientists to design targeted optimization strategies, ensuring that common-sense reasoning does not completely stall practical AI systems.