| 講演名 | 2005-04-18 関数の時間、領域計算量について 上野 賢哉, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 計算可能な関数のクラスと同様に、FP、FPSPACEといった多くの関数計算量クラスは帰納理論的に特徴付けられることが知られている。これらの結果をもとに、一般の関数計算量クラスに対する演算子という概念を導入する。これにより、時間、領域制約関数計算量クラス間の関係を特徴付ける演算子を構成する。また、出力長が入力長の高々定数しか長くならないような関数のクラスを導入し、これらのクラスと演算子を用いてFP、FPSPACEを特徴付ける。さらに、FPSPACE完全性の概念を定義しFPSPACE完全な関数を示す。 |
| 抄録(英) | Similar to the computable function class, it is known that many function complexity classes like FP and FPSPACE can be expressed by recursion theoretic scheme. Based on these results, we introduce a new notion of operators for general function complexity classes. We construct an operator which characterizes the relation between time and space bounded function complexity classes. Moreover, we introduce new classes composed of functions whose output lengths are restricted to the input length plus some constant and characterize FP and FPSPACE by using these classes and operators. Furthermore, we define a notion of completeness for FPSPACE and show a FPSPACE-complete function. |
| キーワード(和) | 関数計算量クラス / 帰納的関数論 / 演算子 |
| キーワード(英) | Function Complexity Classes / Recursive Function Theory / Operators |
| 資料番号 | COMP2005-4 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2005/4/11(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 関数の時間、領域計算量について |
| サブタイトル（和） | |
| タイトル（英） | On time and space complexity of functions |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 関数計算量クラス / Function Complexity Classes |
| キーワード(2)（和/英） | 帰納的関数論 / Recursive Function Theory |
| キーワード(3)（和/英） | 演算子 / Operators |
| 第 1 著者 氏名（和/英） | 上野 賢哉 / Kenya UENO |
| 第 1 著者 所属（和/英） | 東京大学大学院情報理工学系研究科コンピュータ科学専攻 Department of Computer Science Graduate School of Information Science and Technology the University of Tokyo |
| 発表年月日 | 2005-04-18 |
| 資料番号 | COMP2005-4 |
| 巻番号（vol） | vol.105 |
| 号番号（no） | 7 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |