MAX-2SAT問題の平均時間計算量の解析

スポンサーリンク

概要

• 論文の詳細を見る

• We propose a simple probability model for MAX-2SAT instances for discussing the average-case complexity of the MAX-2SAT problem. Our model is a "planted solution model", where each instance is generated randomly from a target solution. We show that for a large range of parameters, the planted solution (more precisely, one of the planted solution pair) is the optimal solution for the generated instance with high probability. We then give a simple linear time algorithm based on a message passing method, and we prove that it solves the MAX-2SAT problem with high probability for random MAX-2SAT instances under this planted solution model for probability parameters within a certain range.

• 社団法人電子情報通信学会の論文
• 2006-05-17

著者

• 渡辺 治

  東京工業大学大学院情報理工学研究科数理・計算科学専攻

• 渡辺 治

  東京工業大学情報理工学研究科数理・計算科学専攻

• 山本 真基

  東海大理

• 山本 真基

  東京工業大学情報理工学研究科

• 山本 真基

  東京工業大学情報理工学研究科数理・計算科学専攻

• 渡辺 治

  東工大情報理工

• 渡辺 治

  東工大

• 渡辺 治

  東京工業大学

• 渡辺 治

  東京工業大学工学部情報工学科

関連論文

• 5.理論研究の役割(情報処理技術の未来地図,50周年記念特集号)
• 20aEA-10 疎なランダム行列の第1固有値に関するcavity解析(20aEA 情報統計力学,領域11(統計力学,物性基礎論,応用数学,力学,流体物理))
• キャンパス共通認証認可システムの構築と運用(セキュアでサステイナブルなインターネットアーキテクチャ論文)
• 東京工業大学におけるキャンパス共通認証認可システムを用いた安全なソフトウェア配布機構の設計と実装(インターネットアーキテクチャ技術-モバイル、セキュリティ,インターネット、アプリケーション及び一般)
• ハッシュ関数の認証プロトコルへの応用
• On NK-Community Problem (Theoretical Computer Science and its Applications)
• 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の量子探索アルゴリズムの決定性運用法について
• モノポリストゲームのゲーム長(手数)について
• 計算を究める : アルゴリズムと計算複雑さの研究 : 情報処理技術 : 過去十年そして今後の十年
• 25pQK-12 正解が埋め込まれたグラフ等分割問題の統計力学的解析(ネットワーク一般・情報統計力学,領域11,統計力学,物性基礎論,応用数学,力学,流体物理)
• MAX-2SAT問題の平均時間計算量の解析
• MAX-2SAT問題の平均時間計算量の解析
• A Message Passing Algorithm for MAX2SAT(New Trends in Theory of Computation and Algorithm)
• 大学内の業務・システムと連携するキャンパス共通認証認可システムの構築と運用
• 弱いランダム仮定の元での公開鍵暗号の強秘匿性について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
• On generating instances for MAX2SAT with optimal solutions (Evolutionary Advancement in Fundamental Theories of Computer Science)
• MAX2SATの解答付き例題生成アルゴリズムの提案
• A_009 An Improved Upper Bound for the Three Domatic Number Problem
• BS-8-10 東京工業大学におけるキャンパス共通認証認可システムを用いた安全なソフトウェア配布機構(BS-8. セキュア、スケーラブルでサステイナブルなキャンパス情報システム,シンポジウムセッション)
• 電子情報通信と離散数学(電子情報通信と数学)
• 計算の複雑さの平均的な解析について(計算量理論の諸相 : その基礎的研究)
• SATを解くO^^〜(1.234^m)時間決定性アルゴリズム
• 3-SATを解くあるローカルサーチアルゴリズムの上界の別証明
• 3-SATを解くあるローカルサーチアルゴリズムの上界の別証明
• 情報セキュリティ技術と計算の複雑さの理論 (特集 暗号化とセキュリティ--アルゴリズムとプロトコル)
• 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* アルゴリズムの提案と多重配列アラインメント問題への応用
• 重み付き乱択最適選好マッチング
• 計算論から見たランダムネス (特集 予測と発見)
• 確率的情報処理と統計力学--様々なアプローチとそのチュートリアル(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)
• 計算複雑さの理論 : 我々は何を研究しているのか?
• でたらめさを利用した計算--「乱択アルゴリズム」の世界 (特集 計算とは何か)
• 計算複雑さの研究って?
• NP-解探索における質問計算量について
• [招待講演]新学術領域「計算限界解明」発足にあたって
• NP-解探索における質問計算量について(一般)

もっと見る 閉じる

スポンサーリンク