情報エントロピーに基づく関数の複雑度解析
スポンサーリンク
概要
- 論文の詳細を見る
情報エントロピーを用いて関数の複雑度を評価する方法を確立した. ここで定義した複雑度は「情報複雑度 information complexity」と名付ける. まず, 定義を与えた後, この定義が自然であることを示すためのいくつかの簡単な性質を述べる. ここで, Shannonの「相互情報量」の拡張が必要であった. 次に, 論理関数に対し情報複雑度による評価を適用し, 等重率の仮定の下でいくつかの有用な結果の得られることを示す. 特に, 論理関数の変換群に対して, 情報複雑度を用いた不変量の完全系が導入出来ることが予想される. およそすべての情報の変換を伴った操作は「関数」と見なすことが出来る. このような関数に情報エントロピーという明確な意味を持つ量に基礎をおいて複雑度が導入出来たことは, 情報処理一般を定量的に評価するための理論的基盤が与えられたことを意味する.
- 一般社団法人情報処理学会の論文
- 1997-09-19