2019-12-10T02:16:41Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001281092017-03-31T05:35:42Z06504:08089:08090
Complexity Analysis of Boolean Functions by Information Entropy情報エントロピーによる論理関数の複雑度解析enghttp://id.nii.ac.jp/1001/00128294/Conference Paperhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=128109&item_no=1&attribute_id=1&file_no=1龍谷大学龍谷大学京都コンピュータ学院中川, 晃成森井, 義之萩原, 宏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.AN00349328全国大会講演論文集第51回基礎理論と基礎技術47481995-09-202015-01-20