| 講演名 | 1998/3/19 非線形符号の半径及び被覆半径に対する近似アルゴリズム 伊東 利哉, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 符号の性能評価において重要な(幾何学的)量である被覆半径及び半径を求める問題の複雑さについて検討する.これまでに, (適当な定式化のもとで)これらの問題は極めて困難であることが知られている.実際, 線形符号が生成行列で与えられるとき, その半径及び被覆半径を求める問題はΣ^p_<2->完全であることが示されており, また, (ある種の)非線形符号がその符号語の全体で与えられるとき, その半径及び被覆半径を求める問題はNP-完全であることが示されている.そこで, 本研究では, まずこれらの問題を"最小化問題"として定式化し, それに対する近似解を求めることについて考察する.そして, P≠NPという仮定のもとで, ある種の非線形符号に関しては, いかなる定数に対しても, 半径及び被覆半径の値をその最適解の定数倍以下で求める多項式時間アルゴリズムは存在しないことを示す. |
| 抄録(英) | For a code C over GF(2), the radius and covering radius of C are useful metric properties of C and play important roles in the analysis of C.In general, the decision problem for the radius and covering radius of C is computationally hard.Indeed, the decision problem for the covering radius of linear codes over GF(2)is Il^p_<2->complete and the decision problems for the radius and covering radius of nonlinear general (not necessarily linear)codes over GF(2)is NP-complete. In this paper, we first formalize those decision problems for the radius and covering radius of codes over GF(2)as minimization problems, i.e., MINIMUM RADIUS and MINIMUM COVERING RADIUS of codes over GF(2), respectively.Then we show that MINIMUM RADIUS and MINIMUM COVERING RADIUS of codes over GF(2)are hard to approximate within any constant ratio unless P=NP. |
| キーワード(和) | 近似アルゴリズム / 非線形符号 / 半径 / 被覆半径 |
| キーワード(英) | Approximation Algorithms / Nonlinear Codes / Radius / Covering Radius |
| 資料番号 | |
| 発行日 |
| 研究会情報 | |
| 研究会 | ISEC |
|---|---|
| 開催期間 | 1998/3/19(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Security (ISEC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 非線形符号の半径及び被覆半径に対する近似アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | Approximating Radius and Covering Radius of Nonlinear Codes Is Hard |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 近似アルゴリズム / Approximation Algorithms |
| キーワード(2)（和/英） | 非線形符号 / Nonlinear Codes |
| キーワード(3)（和/英） | 半径 / Radius |
| キーワード(4)（和/英） | 被覆半径 / Covering Radius |
| 第 1 著者 氏名（和/英） | 伊東 利哉 / TOSHIYA ITOH |
| 第 1 著者 所属（和/英） | 東京工業大学大学院総合理工学研究科物理情報工学専攻 Department of Information Processing Interdisciplinary Graduate School of Science and Engineering Tokyo Institute of Technology |
| 発表年月日 | 1998/3/19 |
| 資料番号 | |
| 巻番号（vol） | vol.97 |
| 号番号（no） | 612 |
| ページ範囲 | pp.- |
| ページ数 | 12 |
| 発行日 | |