情報エントロピーによる論理関数の複雑度解析

概要

論文の詳細を見る
We shall present here a new scale of complexity of Boolean functions. This measure is based upon information entropy and thus will be called information complexity. In fact, our definition of information complexity will be given in terms of 'conditional mutual information. ' Although we restrict ourselves to the complexity of Boolean functions, information complexity is also applicable to the investigation on the complexity of any type of functions. Being defined in terms of information entropy it can be considered as an ultimate scale of complexity of functions over probabilistic variables. As a specific application, we shall be involved in evaluating the complexity of arithmetic operations on computers. An arithmetic operation between two n-bit numbers can be regarded as a collection of n-Boolean functions having 2n-input Boolean variables. Complexity of arithmetic operations can thus be derived from that of Boolean functions. We shall here clarify the necessity of introducing this new scale of complexity of Boolean functions, illustrate the essential idea on information complexity and make some remarks upon representation systems of numbers on which arithmetic operations are defined.
一般社団法人情報処理学会の論文
1995-09-20