Interior and Exterior Functions of Boolean Functions
Interior and Exterior Functions of Boolean Functions
复制标题
布尔函数的内部和外部函数
DOI：
10.1016/0166-218x(95)00092-6
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
T. Ibaraki
中科院分区：
文献类型：
--
作者：
K. Makino;T. Ibaraki
为了研究布尔函数的稳定性，我们定义了布尔函数f的内函数、外函数和层，并考虑了与这些定义相关的三个问题：interior、external和layer。我们证明了即使f被限制为一个正函数，LAYER是NP困难的，并且除非P=NP，否则内部和外部没有多项式总时间算法。然而，对于2单调正函数f， LAYER可以在多项式时间内求解，并且存在INTERIOR和external的增量多项式算法。
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.
单调对偶化及相关主题
DOI：
--
发表时间：
2020
期刊：
影响因子：
--
作者：
112.Yuta Halvorson;Naoki Hasimoto;Kazuhisa Makino
通讯作者：
Kazuhisa Makino