TY - JOUR
T1 - Interior and exterior functions of positive Boolean functions
AU - Makino, Kazuhisa
AU - Ono, Hirotaka
AU - Ibaraki, Toshihide
N1 - Funding Information:
This work was supported in part by Grants-in-Aid for Scientific Research of the Ministry of Education, Culture, Sports, Science and Technology of Japan. The authors thank the anonymous referee for her/his helpful and constructive comments which improved the presentation of this paper.
PY - 2003/8/23
Y1 - 2003/8/23
N2 - 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 first answer the question about the complexity of α-INTERIOR left open in Makino and Ibaraki (Discrete Appl. Math. 69 (1996) 209-231); 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.
AB - 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 first answer the question about the complexity of α-INTERIOR left open in Makino and Ibaraki (Discrete Appl. Math. 69 (1996) 209-231); 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.
UR - https://www.scopus.com/pages/publications/0041386580
UR - https://www.scopus.com/pages/publications/0041386580#tab=citedBy
U2 - 10.1016/S0166-218X(02)00602-9
DO - 10.1016/S0166-218X(02)00602-9
M3 - Article
AN - SCOPUS:0041386580
SN - 0166-218X
VL - 130
SP - 417
EP - 436
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
IS - 3
ER -