Reasoning With Qualitative Probabilities Can Be Tractable
  We recently described a formalism for reasoning with if-then rules that re
expressed with different levels of firmness [18]. The formalism interprets
these rules as extreme conditional probability statements, specifying orders of
magnitude of disbelief, which impose constraints over possible rankings of
worlds. It was shown that, once we compute a priority function Z+ on the rules,
the degree to which a given query is confirmed or denied can be computed in
O(log n`) propositional satisfiability tests, where n is the number of rules in
the knowledge base. In this paper, we show that computing Z+ requires O(n2 X
log n) satisfiability tests, not an exponential number as was conjectured in
[18], which reduces to polynomial complexity in the case of Horn expressions.
We also show how reasoning with imprecise observations can be incorporated in
our formalism and how the popular notions of belief revision and epistemic
entrenchment are embodied naturally and tractably.
