文献

J-GLOBAL ID：201602207654492086   整理番号：16A0182653

多項式時間測度とランダム性について

Polynomial-time computable measure and randomness

著者 (1件)： 河村彰星 (東大)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 115  号： 344(COMP2015 30-36)  ページ： 27-28  発行年： 2015年11月24日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 短報  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 無限ビット列z∈{0,1}^Nが「ランダム」であることの定義の一つは,その始片のみを見て後のビットを予想するのが殆ど不可能であることである。この予想者にどれだけの能力を許すかによって,計算可能ランダム性,多項式時間ランダム性などが定義される。更に実数のランダム性を,その二進展開がランダムであることを以て定義できる。この実数のランダム性が自然な概念であるには,「二進展開という特定の表現法に依らない」ことを期待したいであろう。このことは或る程度まで知られていたが,その証明は煩雑であったり限定的であったりした。本稿では実数の多項式時間ランダム性が,確率測度の多項式時間性を用いて特徴づけられることを示す。すなわち実数が多項式時間ランダムであるのは,如何なる多項式時間測度もその実数に集中しないときである。更に,単調な連続函数は殆ど至る所で微分可能であるというルベグの定理に対応するランダム性としても特徴づけられる。これは冒頭の予想者が,実数の二進展開において次のビットを予想するに限らず,より一般的な方法で実数の位置に関する見立てを述べるのを許すことに対応する。本発表は宮部氏との共同研究に基づき,その結果の一部を紹介するものである。(著者抄録)

シソーラス用語： *計算理論 ,  *時間 ,  *数学的性質 ,  確率測度 ,  実数 ,  関数 ,  性質 ,  数列 ,  データ型 ,  計算可能性
準シソーラス用語： 2進数列 ,  ビット列パターン ,  *ランダム性 ,  *多項式時間 ,  単調性 ,  連続関数

分類 (2件)： 計算理論  (JB02000A) ,  システム・制御理論一般  (IA02010H)

タイトルに関連する用語 (3件)： 多項式時間 ,  測度 ,  ランダム性