| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2007-06-29 10:30 NP困難問題における最悪時困難性からの平均時困難性証明への試み ○河内亮周・渡辺 治（東工大）  COMP2007-21 |
|
| 抄録 | （和） | 最悪時困難性の仮定から平均時困難性を持つ問題を構成することは計算量理論や暗号理論において非常に重要な課題である．本稿では，NP困難問題が最悪時に効率良く解けないことを仮定して，ある標本可能分布の下で生起したインスタンスが正の場合に高い確率で効率良く解くことができないようなNP型探索問題とクラスDPに属する決定問題を構成する． |
| （英） | It is significant in the computational complexity theory and the foundations of cryptography to construct problems hard on average from worst-case hardness assumptions. We construct NP search and DP decision problems that are not efficiently solvable with high probability over positive instances w.r.t. some samplable distributions under the assumption that NP-hard problems are not efficiently solvable in the worst case. |
|
| キーワード | （和） | 平均計算量 / NP困難問題 / 標本可能分布 / 最悪時/平均時困難性帰着 / / / / |
| （英） | average-case complexity / NP-hard problems / samplable distributions / worst case to average case reductions / / / / | |
| 文献情報 | 信学技報, vol. 107, no. 127, COMP2007-21, pp. 25-32, 2007年6月. | |
| 資料番号 | COMP2007-21 | |
| 発行日 | 2007-06-22 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2007-21 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2007-06-29 - 2007-06-29 |
| 開催地（和） | 北海道大学 |
| 開催地（英） | Hokkaido University |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2007-06-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | NP困難問題における最悪時困難性からの平均時困難性証明への試み |
| サブタイトル（和） | |
| タイトル（英） | Towards closing a gap between worst-case and average-case NP hardness |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 平均計算量 / average-case complexity |
| キーワード(2)（和/英） | NP困難問題 / NP-hard problems |
| キーワード(3)（和/英） | 標本可能分布 / samplable distributions |
| キーワード(4)（和/英） | 最悪時/平均時困難性帰着 / worst case to average case reductions |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 河内 亮周 / Akinori Kawachi / カワチ アキノリ |
| 第1著者 所属（和/英） | 東京工業大学 (略称： 東工大) Tokyo Institute of Technology (略称： Tokyo Inst. of Tech.) |
| 第2著者 氏名（和/英/ヨミ） | 渡辺 治 / Osamu Watanabe / ワタナベ オサム |
| 第2著者 所属（和/英） | 東京工業大学 (略称： 東工大) Tokyo Institute of Technology (略称： Tokyo Inst. of Tech.) |
| 第3著者 氏名（和/英/ヨミ） | / / |
| 第3著者 所属（和/英） | (略称： ) (略称： ) |
| 第4著者 氏名（和/英/ヨミ） | / / |
| 第4著者 所属（和/英） | (略称： ) (略称： ) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2007-06-29 10:30:00 |
| 発表時間 | 25分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2007-21 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | no.127 |
| ページ範囲 | pp.25-32 |
| ページ数 | 8 |
| 発行日 | 2007-06-22 (COMP) |
[研究会発表申込システムのトップページに戻る]