论文标题
证书复杂性和嵌套管功能的对称性
Certificate complexity and symmetry of nested canalizing functions
论文作者
论文摘要
布尔嵌套的载口功能（NCF）在分子调节网络，工程和计算机科学中具有重要的应用。在本文中，我们研究了他们的证书复杂性。对于两个布尔值$ b \ in \ {0,1 \} $，我们获得了$ b $ - 验证复杂性的公式，因此，我们为NCF的证书复杂性公式提供了直接证明。对称性是布尔函数的另一个有趣属性，我们大大简化了有关NCF部分对称性的一些最新定理的证明。我们还描述了$ s $ symmetric NCFS的代数正常形式。我们获得了$ n $ -variable $ s $ s $ symmetric boolean ncfs ncfs的一般公式，$ s = 1，\ dots，n $。特别是，我们列举了强烈的不对称布尔NCF。
Boolean nested canalizing functions (NCFs) have important applications in molecular regulatory networks, engineering and computer science. In this paper, we study their certificate complexity. For both Boolean values $b\in\{0,1\}$, we obtain a formula for $b$-certificate complexity and consequently, we develop a direct proof of the certificate complexity formula of an NCF. Symmetry is another interesting property of Boolean functions and we significantly simplify the proofs of some recent theorems about partial symmetry of NCFs. We also describe the algebraic normal form of $s$-symmetric NCFs. We obtain the general formula of the cardinality of the set of $n$-variable $s$-symmetric Boolean NCFs for $s=1,\dots,n$. In particular, we enumerate the strongly asymmetric Boolean NCFs.
