A state-of-the-art method for two-level logic minimization has been proposed by
Coudert [2]. It uses OBDDs to represent not only Boolean functions but also the sets of
their prime implicants to overcome the explosion of the number of prime implicants [3].
Their method has been shown to be quite efficient in practical use but its computational
complexity has been scarcely clarified. In this paper, it will be shown that there exists
a monotone function that has an O(n) size DNF and an exponential lower bound
in OBDD size, which is a solution to open questions concerned with computational
complexity [2].