P完全な2人完全情報ゲーム問題に対応する数え上げ問題はPに属する
スポンサーリンク
概要
- 論文の詳細を見る
NP完全な決定問題に対応する数え上げ問題はNP困難である. しかしながら, NP完全問題に対応する数え上げ問題でNPに属する問題は現時点では知られていない. 一方, Pに属する決定問題に対応する数え上げ問題はPに属するとは限らないことが報告されている. 現在研究されている計算量クラスは決定問題のクラスであるが, 上記の事実から, NPに属する問題はやはり本質的にPに属する問題より難しく, 従って, NP に属する問題を少しだけ難しくしただけで, その問題はNPより難しいクラスに属してしまうことになるように思われる. したがって, Pに属する問題に対応する数え上げ問題の計算量を研究することはP=NP問題に対する何らかの洞察を与えるだろう. 本論文では, P完全な2人完全情報ゲーム問題を考察し, 先手の必勝手を数え上げる具体的方法を示し, 数え上げがO(n^^4)時間でできることを示す.
- 1996-03-25
著者
関連論文
- 固定費付き輸送問題のための遺伝的アルゴリズムの提案と数値実験
- 暗号通信を用いたIP通信拡散手法
- 数値的三次元マッチング問題を利用した公開鍵暗号系の設計の設計
- P完全な2人完全情報ゲーム問題に対応する数え上げ問題はPに属する
- ナップザック問題が効率的に解けるための自明でない十分条件
- 部分グラフ彩色問題の計算量
- 道発見ゲーム問題の計算量
- ある制限されたチャイニーズ・ポストマン問題の計算量
- ある制限されたチャイニーズ・ポストマン問題の計算量(計算モデルと計算の複雑さに関する研究)
- ある制限されたチャイニーズ・ポストマン問題の計算量
- 2人ゲームにおける必勝手を数えあげる多項式時間アルゴリズム
- 容量なし施設配置問題のための遺伝的アルゴリズムの提案
- L-003 パケットフィルタリング機能を搭載したNICによるDoS攻撃対策(ネットワーク・セキュリティ,一般論文)
- 暗号通信を用いたIP通信拡散手法
- 暗号通信を用いたIP通信拡散手法
- 暗号通信を用いたIP通信拡散手法
- 不定方程式を用いた公開鍵暗号系の設計
- アドホックネットワークのためのチェックポイントプロトコルとその評価(会場B)
- アドホックネットワークのためのチェックポイントプロトコルとその評価(セッション4-A:アドホックネットワーク(2))
- チェックポイントプロトコル実行中のトポロジ変化を考慮した無線マルチホップネットワークのためのチェックポイントプロトコル(アドホックネートワーク(2))
- チェックポイントプロトコル実行中のトポロジ変化を考慮した無線マルチホップネットワークのためのチェックポイントプロトコル(アドホックネートワーク(2))
- アドホックネットワークのためのチェックポイントプロトコル(分散システム)
- アドホックネットワークのためのチェックポイントプロトコル(分散システム)
- 移動コンピュータの移動を考慮した無線マルチホップネットワークのためのチェックポイントプロトコル(セッション2: 分散システム・プロトコル)
- 移動コンピュータの移動を考慮した無線マルチホップネットワークのためのチェックポイントプロトコル(セッション2: 分散システム・プロトコル)
- アドホックネットワークのためのチェックポイントプロトコル(セッション1: プロトコル)
- [電子情報通信学会フェロー受賞記念講演]大学卒業後の40年を振り返って
- アドホックネットワークのためのチェックポイントプロトコルとその評価(セッション4-A:アドホックネットワーク(2))
- 複数の異なるチェックポイントの同時実行に対応したアドホックネットワークのためのチェックポイントプロトコル
- Generalizations of operator Shannon inequality based on Tsallis and Renyi relative entropies (Operator monotone functions and related topics)
- Extensions of relative operator entropies and operator $\alpha$-divergence (Operator monotone functions and related topics)