A Logic for Reasoning about Upper Probabilities
This work addresses foundational issues in AI and reasoning under uncertainty, providing a formal framework for handling imprecise probabilities, but it is incremental as it builds on existing logical and probabilistic theories.
The paper tackles the problem of reasoning about uncertainty modeled by sets of probability measures, which assign intervals to events, by presenting a propositional logic with a sound and complete axiomatization. The result shows that the satisfiability problem for this logic is NP-complete, matching the complexity of standard propositional logic.
We present a propositional logic to reason about the uncertainty of events, where the uncertainty is modeled by a set of probability measures assigning an interval of probability to each event. We give a sound and complete axiomatization for the logic, and show that the satisfiability problem is NP-complete, no harder than satisfiability for propositional logic.