Ashok K. Chandra, Prabhakar Raghavan, et al.
Computational Complexity
It is shown that any Boolean expression in disjunctive normal form having k conjuncts, can have at most 2k prime implicants. However, there exist such expressions that have 2 k 2 prime implicants. It is also shown that any Boolean expression on n distinct propositional variables can have at most O( 3n n) prime implicants, and that there exist expressions with ω( 3n n prime implicants. © 1978.
Ashok K. Chandra, Prabhakar Raghavan, et al.
Computational Complexity
Ashok K. Chandra, Harry R. Lewis, et al.
STOC 1981
Ashok K. Chandra
FOCS 1978
Ashok K. Chandra, David Harel
STOC 1979