VARIABLE AND TERM REMOVAL FROM BOOLEAN-FORMULAS

Given a Boolean formula in disjunctive normal form, the variable delet ion control set problem consists in finding a minimum cardinality set of variables whose deletion from the formula results in a DNF satisfyi ng some prescribed property. Similar problems can be defined with resp ect to the fixation of variables or the deletion of terms in a DNF. In this paper, we investigate the complexity of such problems for a broa d class of DNF properties.