Variable and term removal from Boolean formulae

✍ Scribed by Yves Crama; Oya Ekin; Peter L Hammer

• Book ID: 104294707
• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 921 KB
• Volume: 75
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(96)00028-5

✦ Synopsis

Given a Boolean formula in disjunctive normal form, the variable deletion control set problem consists in finding a minimum cardinality set of variables whose deletion from the formula results in a DNF satisfying some prescribed property. Similar problems can be defined with respect 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 broad class of DNF properties.