Interior and exterior functions of positive Boolean functions

✍ Scribed by Kazuhisa Makino; Hirotaka Ono; Toshihide Ibaraki

• Book ID: 104294156
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 237 KB
• Volume: 130
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(02)00602-9

✦ Synopsis

The interior and exterior functions of a Boolean function f were introduced in Makino and Ibaraki (Discrete Appl. Math. 69 (1996) 209-231), as stability (or robustness) measures of the f. In this paper, we investigate the complexity of two problems -INTERIOR and -EXTERIOR, introduced therein. We ÿrst answer the question about the complexity of -INTERIOR left open in Makino and Ibaraki (Discrete Appl. Math. 69 (1996) ; it has no polynomial total time algorithm even if is bounded by a constant, unless P = NP. However, for positive h-term DNF functions with h bounded by a constant, problems -INTERIOR and -EXTERIOR can be solved in (input) polynomial time and polynomial delay, respectively. Furthermore, for positive k-DNF functions, -INTERIOR for two cases in which k = 1, and and k are both bounded by a constant, can be solved in polynomial delay and in polynomial time, respectively.