Sensitivity, Block Sensitivity, and Certificate Complexity of Unate Functions and Read-Once Functions
Sensitivity, Block Sensitivity, and Certificate Complexity of Unate Functions and Read-Once Functions
复制标题
Unate 函数和只读函数的灵敏度、块灵敏度和证书复杂性
DOI：
10.1007/978-3-662-44602-7_9
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Hiroki Morizumi
中科院分区：
文献类型：
--
作者：
Hiroyuki Takizawa;Kentaro Koyama;Katsuto Sato;Kazuhiko Komatsu;and Hiroaki Kobayashi;Hiroki Morizumi
敏感度、块敏感度和证书复杂度是布尔函数的复杂度度量。在本文中，我们证明了这三个复杂性措施是彼此相等的，如果一个布尔函数是一个unate函数或read-once函数。我们还证明了三个复杂性措施的read-once函数的下界。作为结果的应用，unate函数和read-once函数的决策树复杂度的上界是函数灵敏度的平方。
Sensitivity, block sensitivity, and certificate complexity are complexity measures for Boolean functions. In this paper, we prove that these three complexity measures are equal to each other if a Boolean function is a unate function or a read-once function. We also provetight lower bounds for the three complexity measures of read-once functions. As an application of our results, the decision tree complexity of unate functions and read-once functions is upper bounded by the square of the sensitivity of the function.