効果的な複雑さ

有効複雑性は、1996年にマレー・ゲルマンとセス・ロイドが発表した論文で定義された複雑性の尺度であり、システム内の非ランダム情報の量を測定することを試みるものである。 ^[1]^[2]システム内の情報のどの部分をランダムとして無視するかという主観的な判断に依存していると批判されてきた。^[3]

参照

参考文献

^ Gell-Mann, Murray; Lloyd, Seth (1996). 「情報尺度、実効複雑性、そして総情報量」. Complexity . 2 (1): 44– 52. Bibcode :1996Cmplx...2a..44G. doi :10.1002/(SICI)1099-0526(199609/10)2:1<44::AID-CPLX10>3.0.CO;2-X.
^ Ay, Nihat; Muller, Markus; Szkola, Arleta (2010). 「実効複雑性と論理深度との関係」. IEEE Transactions on Information Theory . 56 (9): 4593– 4607. arXiv : 0810.5663 . doi :10.1109/TIT.2010.2053892. S2CID 2217934.
^ マカリスター、ジェームズ・W. (2003). 「情報量の尺度としての実効複雑性」.科学哲学. 70 (2): 302– 307. doi :10.1086/375469. S2CID 120267550.

外部リンク

http://www.cs.brandeis.edu/~pablo/complex.maker.html

P≟NP

この理論計算機科学関連の記事はスタブです。記事を拡張することでWikipediaに貢献できます。

[1] Gell-Mann, Murray; Lloyd, Seth (1996). 「情報尺度、実効複雑性、そして総情報量」. Complexity . 2 (1): 44– 52. Bibcode :1996Cmplx...2a..44G. doi :10.1002/(SICI)1099-0526(199609/10)2:1<44::AID-CPLX10>3.0.CO;2-X.

[2] Ay, Nihat; Muller, Markus; Szkola, Arleta (2010). 「実効複雑性と論理深度との関係」. IEEE Transactions on Information Theory . 56 (9): 4593– 4607. arXiv : 0810.5663 . doi :10.1109/TIT.2010.2053892. S2CID 2217934.

[3] マカリスター、ジェームズ・W. (2003). 「情報量の尺度としての実効複雑性」.科学哲学. 70 (2): 302– 307. doi :10.1086/375469. S2CID 120267550.