多項式の前処理つき計算の複雑さについて
スポンサーリンク
概要
- 論文の詳細を見る
変数x_1, x_2, …, x_pの多項式で, その係数が他の変数a_1, a_2, …, a_qの多項式であるようなものの複数個の組が与えられたとき, それらの値を計算するのに必要な乗算の回数のひとつの下限を与えた. すなわち, x_1, …, x_pの多項式として積和型に展開したときの定数項以外の係数(aについての多項式)で, "多項式に関して独立"なものがs個あれば, それらの値の計算には, a_1, …, a_qについての前処理を許しても, 少なくともs/2回の乗算が必要である.
- 一般社団法人情報処理学会の論文
- 1979-07-15
著者
関連論文
- 多値論理 (<特集>非標準論理とその応用)
- 研究の環境 : 極限状況からのアプローチ(8.環境)(極限へのアプローチ)
- 4. 行列積の漸近的計算量 (アルゴリズムの最近の動向)
- 双端キューの並列結合によるソーティングについて
- 計算の複雑さについて
- 安全クイックソート
- Dequesによる順列のソーティングについて
- 多項式の前処理つき計算の複雑さについて
- 多値論理関数族の完全性--歴史と… (多値論理)
- 離散数学とはなにか (離散数学のすすめ--現代数学の新天地)
- アルゴリズムについて (アルゴリズムの発見)
- アルゴリズムとグラマ (生成発展系--アルゴリズムとグラマ)
- オ-トマトン系の完全性 (オ-トマトン構造)
- 言語と数学 (言語)
- 知識構造と数学 (知識構造)
- 論理素子集合の順序回路に基づく完全性