Certificate complexity and symmetry of Boolean nested canalizing functions.

Boolean nested canalizing functions (NCFs) have important applications in molecular regulatory networks, engineering and computer science. In this paper, we study the certificate complexity of NCFs. For $b=0,1$, we obtain the formula of $b$-certificate complexity of NCFs. Consequently, we develop a direct proof of the certificate complexity formula of NCFs. Symmetry is another interesting property of Boolean functions. 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,...,n$. Particularly, we obtain the cardinality formula for the set of strongly asymmetric Boolean NCFs.