Combining uncertain evidence Logic and complexity

This dissertation addresses the challenge of combining uncertain, partial and possibly mutually contradictory evidence with a focus on logic and computational complexity. In this context, evidence is represented as a subset of a universe; uncertainty as values between 0 and 1; partiality as ignorance about subsets that are not presented as evidence; and mutual contradiction as empty intersection. The main problem is (1) to combine such evidence to obtain a normalized body of evidence, where certainty values sum up to 1. A relevant extension is (2) to compute degrees of belief based on that combined evidence. We explore problems (1) and (2) via three different approaches. First, we present two well-established solutions to these problems: Dempster-Shafer theory and topological models of evidence. We define a common vocabulary between both frameworks and use them as the basis of our solution for (1) and (2). Second, we present a modal logic to compare propositions in terms of (a) their degree of belief, and (b) the certainty of their evidential support. Lastly, we analyze the computational complexity of (1) and (2).