Department of Applied Mathematics & Physics, Kyoto Univiversity

Technical Report #99011 (May, 1999)

Interior and exterior functions of positive Boolean functions
by Kazuhisa Makino, Hirotaka Ono and Toshihide Ibaraki

The interior function and exterior function of a Boolean function $f$ are introduced~\cite{makino2} in order to express its stability and robustness properties. In this paper, we investigate the complexity of two problems $\alpha$-INTERIOR and $\alpha$-EXTERIOR. We first answer the question about the complexity of $\alpha$-INTERIOR left open in \cite{makino2}; it has no polynomial total time algorithm even if $\alpha$ is bounded by a constant, unless P$=$NP. However, for positive $h$-term DNF functions with $h$ bounded by a constant, problem $\alpha$-INTERIOR and $\alpha$-EXTERIOR can be solved in (input) polynomial time and polynomial delay, respectively. Furthermore, for positive $k$-DNF functions, $\alpha$-INTERIOR for two cases in which $k=1$, and $\alpha$ and $k$ are both bounded by a constant, can be solved in polynomial delay and in polynomial time, respectively.