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.