決定森の族の計算能力

スポンサーリンク

概要

論文の詳細を見る
本稿では, Nisan, Rudich, Saks(FOCS'94)によって提起された, 決定木モデルにおける補助ビット問題について考える.この問題は, 互いに独立なk個の入力に対する論理関数ƒの計算を, ƒ自身の計算量より真に小さな計算量で行うためには, いくつの補助ビットが必要であるかを問う問題である.BeigelとHirst(STOC'98)は, 任意の論理関数に対して, 少なくとも⌊log_2k⌋+1個の補助ビットが必要であることを示すと共に, 実際に⌊log_2^k⌋+1個の補助ビットが計算量を減少させる具体的な関数を提示した.本稿では, これと同様の性質を持つ, より計算量の少ない論理関数を提示する.本稿では, また, 深さ1の決定木群に補助ビットを用いた場合の計算能力についても考察し, 更に, 補助ビット問題と闘値ゲートを出力に持つ論理回路モデルにおける計算量との間に密接な関係があることをも明らかにする.
2001-10-12

著者

関連論文

もっと見る

スポンサーリンク