2024-03-28T20:06:07Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000327762023-04-27T10:00:04Z01164:02592:02730:02734
組織化された系の複雑さを測る方法How to Measure the Complexity of Organized Systems Preliminary Reportjpnhttp://id.nii.ac.jp/1001/00032776/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=32776&item_no=1&attribute_id=1&file_no=1Copyright (c) 1988 by the Information Processing Society of JapanNTT情報通信処理研究所岡本, 龍明組織化された系の複雑さを測る一方法を提案する。そのため、情報源に対し、システムコンプレキシティと呼ぶ概念を定義する。また、条件付きシステムコンプレキシティ、及び資源制約システムコンプレキシティを導入する。特に、多項式時間制約条件付きシステムコンプレキシティが、Goldwasserらによって導入された知識コンプレキシティと密接に関連することを示す。さらに、情報源の持つ情報量のみでなく受信者の能力や知識にも依存して決まるような転送情報量を測る一方法を示す。また、複雑度を決定する不完全性並びに実用的測定方法について述べる。最後に、システムコンプレキシティの応用として、計算量理論、通信、及び、生物学的オートマトン理論への応用例を示す。The main purpose of this paper is to present a new way to measure the degree of the complexity of organized systems. For this purpose, we define a new notion of complexity, called system complexity. Conditional system complexity and a resource bounded variant of system complexity are also presented. In particular, we show that the polynomial-time bounded conditional system complexity is closely related to the knowledge complexity introduced by Goldwasser et al. In addition, we show a way to measure the amount of transmitted information from sources to destinations and inference processes in the light of system complexity. Incompleteness and practical measurement are also discussed. Finally, a number of applications to computational complexity, communications, and biological automata theory are presented.AN1009593X情報処理学会研究報告アルゴリズム(AL)198836(1988-AL-001)181988-05-232009-06-30