2024-03-28T23:07:45Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001017002023-04-27T10:00:04Z01164:02592:07425:07606
On Characterizations of Randomized Computation Using Plain Kolmogorov Complexity乱択計算の素朴コルモゴロフ記述量を用いた特徴付けについてenghttp://id.nii.ac.jp/1001/00101678/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=101700&item_no=1&attribute_id=1&file_no=1Copyright (c) 2014 by the Institute of Electronics, Information and Communication Engineers This SIG report is only available to those in membership of the SIG.東京大学大学院情報理工学系研究科東京大学大学院情報理工学系研究科平原, 秀一河村, 彰星接頭辞コルモゴロフ記述量の意味でランダムな文字列の集合に,多項式時間で帰着できる言語のクラス DTTRk は,PSPACE に含まれることが Allender と Friedman と Gasarch によって示されている.一方 DTTRk は BPP を含むことが Buhrman と Fortnow と Koucky と Loff によって示されており,実はこの下界 BPP の方に近いと予想されている.また,接頭辞コルモゴロフ記述量の代わりに素朴コルモゴロフ記述量を用いて定義されるクラス DTTRc も同じような上界を持つことが予想されている.本論文では,これらの予想を支持する結果を示す.はじめに,DTTRc の定義に使うコルモゴロフ記述量に時間制限を付けて得られるクラスが,BPP と PSPACE∩P/poly の間にあることを示す.次に,DTTRc の帰着に制限を付けたクラス DTTRc,α が BPP と PSPACE の間にあることを示す.最後に,更に帰着において入力の対数長の質問のみを許すように制限したクラス P/RC=log が BPP と Σp2∩P/poly の間にあることを示す.Allender, Friedman, and Gasarch recently proved an upper bound of PSPACE for the class DTTRk of decidable languages that are polynomial-time truth-table reducible to the set of prefix-free Kolmogorov-random strings regardless of the universal machine used in the definition of Kolmogorov complexity. It is conjectured that DTTRk in fact lies closer to its lower bound BPP established earlier by Buhrman, Fortnow, Koucky, and Loff. It is also conjectured that we have similar bounds for the analogous class DTTRc defined by plain Kolmogorov randomness. In this paper, we provide further evidence for these conjectures. First, we show that the time-bounded analogue of DTTRc sits between BPP and PSPACE∩P/poly. Next, we show that the class DTTRc,α obtained from DTTRc by imposing a restriction on the reduction lies between BPP and PSPACE. Finally, we show that the class P/RC=log obtained by further restricting the reduction to ask queries of logarithmic length lies between BPP and Σp2∩P/poly.AN1009593X研究報告アルゴリズム(AL)2014-AL-14813172014-06-062014-05-27