On Computing Sensitivity, Block Sensitivity, and Certificate Complexity for Boolean Formulas

スポンサーリンク

概要

• 論文の詳細を見る

• Sensitivity, block sensitivity, and certificate complexity are complexity measures for Boolean functions. If a Boolean function f is given by its truth table, it is known that there exist polynomial-time algorithms computing these three values of f. In this talk, we consider the problem computing sensitivity, block sensitivity, and certificate complexity for Boolean functions given by formulas.

• 2014-02-24

著者

• Hiroki Morizumi

  Interdisciplinary Graduate School of Science and Engineering, Shimane University

関連論文

• On Computing Sensitivity, Block Sensitivity, and Certificate Complexity for Boolean Formulas

スポンサーリンク