NP困難問題における最悪時困難性からの平均時困難性証明への試み
スポンサーリンク
概要
- 論文の詳細を見る
最悪時困難性の仮定から平均時困難性を持つ問題を構成することは計算量理論や暗号理論において非常に重要な課題である.本稿では,NP困難問題が最悪時に効率良く解けないことを仮定して,ある標本可能分布の下で生起したインスタンスが正の場合に高い確率で効率良く解くことができないようなNP型探索問題とクラスDPに属する決定問題を構成する.
- 社団法人電子情報通信学会の論文
- 2007-06-22
著者
-
渡辺 治
東京工業大学大学院情報理工学研究科数理・計算科学専攻
-
渡辺 治
東京工業大学情報理工学研究科数理・計算科学専攻
-
渡辺 治
東工大情報理工
-
河内 亮周
東京工業大学大学院情報理工学研究科数理・計算科学専攻
-
渡辺 治
Tokyo Inst. Technol.
-
WATANABE Osamu
Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology
-
渡辺 治
東工大
-
渡辺 治
東京工業大学
-
渡辺 治
東京工業大学工学部情報工学科
-
河内 亮周
Department of Mathematical and Computing Sciences, Tokyo Institute of Technology
-
河内 亮周
東京工業大学
関連論文
- 5.理論研究の役割(情報処理技術の未来地図,50周年記念特集号)
- 20aEA-10 疎なランダム行列の第1固有値に関するcavity解析(20aEA 情報統計力学,領域11(統計力学,物性基礎論,応用数学,力学,流体物理))
- 計算量理論における乱数(学生/教養のページ)
- キャンパス共通認証認可システムの構築と運用(セキュアでサステイナブルなインターネットアーキテクチャ論文)
- 東京工業大学におけるキャンパス共通認証認可システムを用いた安全なソフトウェア配布機構の設計と実装(インターネットアーキテクチャ技術-モバイル、セキュリティ,インターネット、アプリケーション及び一般)
- ハッシュ関数の認証プロトコルへの応用
- 3充足可能性判定問題3SATの正例題生成手法の解析(並列処理)
- 3充足可能性判定問題3SATの正例題生成手法について
- 量子計算における整数格子問題へのアプローチ(量子情報処理論文)
- 方位選択性問題への理論計算機科学からのアプローチ (離散的アルゴリズムと計算量)
- 百行プログラミングの試み : 情報通信技術の科学的理解のために(科学的リテラシー)
- 最大尤度解探索の計算複雑さ
- NP困難問題における最悪時困難性からの平均時困難性証明への試み
- 教養としてのコンピュータ・サイエンス教育 : 東京工業大学での試み
- メッセージ伝播法によるグラフの分割アルゴリズム
- Pseudo Expectation : A Tool for Analyzing Local Search Algorithms
- 単純な規則で表わされるマルコフ過程の近似解析手法
- LDPC符号に対するランダム復号法の解析
- A-17 On the Influence of Outliers in the Soft Margin SVM Framework
- ブースティング技法のアルゴリズム的考察
- サポートベクトルマシンにおける例外の影響力の定め方について
- 相対化計算の元でのクラスの等価性についての一考察
- 相対化計算の元でのクラスの等価性についての一考察
- Provably Fast Training Algorithms for Support Vector Machines
- TD-1-4 サンプリング技法でエラーを抽出する方法について
- An Improved Randomized Algorithm for 3-SAT (New Developments of Theory of Computation and Algorithms)
- Groverの量子探索アルゴリズムの決定性運用法について
- モノポリストゲームのゲーム長(手数)について
- 計算を究める : アルゴリズムと計算複雑さの研究 : 情報処理技術 : 過去十年そして今後の十年
- 頑健な量子状態復号とルジャンドル列の疑似乱数性
- D-1-5 量子有限オートマトンの類似性判定アルゴリズム(D-1. コンピュテーション)
- 25pQK-12 正解が埋め込まれたグラフ等分割問題の統計力学的解析(ネットワーク一般・情報統計力学,領域11,統計力学,物性基礎論,応用数学,力学,流体物理)
- MAX-2SAT問題の平均時間計算量の解析
- MAX-2SAT問題の平均時間計算量の解析
- A Message Passing Algorithm for MAX2SAT(New Trends in Theory of Computation and Algorithm)
- 大学内の業務・システムと連携するキャンパス共通認証認可システムの構築と運用
- Robust Quantum Algorithms for Oracle Identification (Theoretical Computer Science and its Applications)
- オラクル同定問題に対する頑健な量子アルゴリズム
- ビンとボールのゲームにおける2ビン選択モデルの一般化
- 探索問題における一般的な量子オラクルの質問回数について
- A-1 3関数に対する量子クロー探索アルゴリズム(計算量・量子計算,A.アルゴリズム・基礎)
- 占有問題に対する量子アルゴリズム
- 伸長係数2のコンパクトラウティングアルゴリズム (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
- 弱いランダム仮定の元での公開鍵暗号の強秘匿性について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
- A Lattice-Based Cryptosystem and Proof of Knowledge on Its Secret Key(Theory of Computer Science and Its Applications)
- Multi-Bit Cryptosystems based on Lattice Problems : Extended Abstract(New Trends in Theory of Computation and Algorithm)
- A_009 An Improved Upper Bound for the Three Domatic Number Problem
- BS-8-10 東京工業大学におけるキャンパス共通認証認可システムを用いた安全なソフトウェア配布機構(BS-8. セキュア、スケーラブルでサステイナブルなキャンパス情報システム,シンポジウムセッション)
- 電子情報通信と離散数学(電子情報通信と数学)
- 計算の複雑さの平均的な解析について(計算量理論の諸相 : その基礎的研究)
- Geometric Characterization of Quantum Oracle Identification(New Trends in Theory of Computation and Algorithm)
- 情報セキュリティ技術と計算の複雑さの理論 (特集 暗号化とセキュリティ--アルゴリズムとプロトコル)
- NP型探索問題のテスト例生成問題について
- NP型問題の近似解法の可能性について
- 計算論的学習理論のお話
- 一方向関数のお話し
- TK-7-5 グローバルCOE報告 : 計算世界観の深化と展開(TK-7.情報・電気・電子グローバルCOEの活動と今後の計画,大会委員会企画)
- TK-7-5 グローバルCOE報告 : 計算世界観の深化と展開(TK-7.情報・電気・電子グローバルCOEの活動と今後の計画,大会委員会企画)
- TK-7-5 グローバルCOE報告 : 計算世界観の深化と展開(TK-7.情報・電気・電子グローバルCOEの活動と今後の計画,大会委員会企画)
- TK-7-5 グローバルCOE報告 : 計算世界観の深化と展開(TK-7.情報・電気・電子グローバルCOEの活動と今後の計画,大会委員会企画)
- TK-7-5 グローバルCOE報告 : 計算世界観の深化と展開(TK-7.情報・電気・電子グローバルCOEの活動と今後の計画,大会委員会企画)
- TK-7-5 グローバルCOE報告 : 計算世界観の深化と展開(TK-7.情報・電気・電子グローバルCOEの活動と今後の計画,大会委員会企画)
- TK-7-5 グローバルCOE報告 : 計算世界観の深化と展開(TK-7.情報・電気・電子グローバルCOEの活動と今後の計画,大会委員会企画)
- 超平面ハッシュ関数に基づく分散A* アルゴリズムの提案と多重配列アラインメント問題への応用
- 重み付き乱択最適選好マッチング
- 任意の量子一方向性関数に対するハードコア述語の一般的構成法
- Quantum Biased Oracles (特集:量子計算と量子情報)
- 定数ラウンドで復元可能な合理的秘密分散
- 計算論的安全性に基づく量子暗号
- 任意の量子一方向性関数に対するハードコア述語の一般的構成法
- 素体上多項式に対する計算困難な関数
- Gowers一様性による剰余関数と多項式の相関の評価 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- Quantum Sampling for Balanced Allocations(Foundations of Computer Science)
- 計算論から見たランダムネス (特集 予測と発見)
- 確率的情報処理と統計力学--様々なアプローチとそのチュートリアル(7)乱択アルゴリズムへの招待
- r-of-k閾値関数に対するブースティングを用いた学習
- マルコフ過程の近似解析と乱択アルゴリズムの解析への応用
- 平均計算時間に基づく計算複雑さの研究について(計算量理論とその周辺)
- 確率的アルゴリズムにおける効率・正解率間のトレードオフ関係について
- 6. 確率的アルゴリズム (アルゴリズムの最近の動向)
- On Reliability and Efficiency of Probabilistic Algorithms (形式言語理論とオ-トマトン理論)
- A Derivation of Cook's Simulation Algorithm by Program Transformation (Studies on Computational Complexities and Related Topics)
- DS-1-7 On Coppersmith's Technique and its Limit
- Complexity-Theoretical Quantum List Decoding and Applications to Quamtum Hardcore Functions (計算理論とアルゴリズムの新展開 RIMS研究集会報告集)
- On Polynomial Time Many-One Completeness of One-Way Functions : Preliminary Report
- 計算複雑さの理論 : 我々は何を研究しているのか?
- Rational Secret Sharing for Non-Simultaneous Channels (情報理論)
- でたらめさを利用した計算--「乱択アルゴリズム」の世界 (特集 計算とは何か)
- 計算複雑さの研究って?
- リスト復号の質問計算量
- 非同時通信路における合理的秘密分散(情報セキュリティ)
- NP-解探索における質問計算量について
- A Fourier analytic approach to list-decoding for sparse random linear codes (New Trends in Theoretical Computer Science)
- Query Complexity of Witness Finding (コンピュテーション)
- [招待講演]新学術領域「計算限界解明」発足にあたって
- NP-解探索における質問計算量について(一般)
- 計算複雑さへの招待(2) : アルゴリズムから攻める計算複雑さの下界証明(【特別企画】「計算限界解明」チュートリアル講演第2回)
- Quantum-Advised Algorithms for Biased Oracles (コンピュテーション)
- 非同時通信路における合理的秘密分散