Interior and exterior functions of Boolean functions Original Research Article

We define the interior function, exterior function and layer of a Boolean function f in order to investigate its stability properties, and consider three problems INTERIOR, EXTERIOR and LAYER associated with such definitions. We show that even if f is restricted to be a positive function, LAYER is NP-hard and there is no polynomial total time algorithm for INTERIOR and EXTERIOR, unless P=NP. However, for a 2-monotonic positive function f, LAYER can be solved in polynomial time and there exist incrementally polynomial algorithms for INTERIOR and EXTERIOR.