Appendix

The supplementary material is organized as follows. In section A, we provide a proof that there is no polynomial-time algorithm for the problem of computing minimum δ-sufficient reasons (unless PTIME = NP), even when δ is a fixed value. In section B, we provide a proof that there is no polynomial-time algorithm for the problem of computing minimal δ-sufficient reasons (unless PTIME = NP). In particular, we define in this section a decision problem that we prove to be NP-hard in Section B.1, and then we show in Section B.2 that this decision problem can be solved in polynomial-time if there exists a polynomial-time algorithm for the problem of computing minimal δ-sufficient reasons. In Section C, we provide a proof that minimum and minimal δ-sufficient reasons can be computed in polynomial-time when the split number (defined in Section 5.1) is bounded. Finally, we provide in Section D a proof of Lemma 1, which completes the proof of tractability of the problem of computing minimal δ-sufficient reasons for each class of monotone Boolean models for which the problem of counting positive completions can be solved in polynomial time.