単純確率ゲームの普遍最適戦略に関する計算複雑性
スポンサーリンク
概要
- 論文の詳細を見る
単純確率ゲームは二人のプレイヤーによって部分的に移動が制御されるマルコフ過程上での二人ゼロ和ゲームである。このゲームの最適戦略を求めるアルゴリズムは数多く提案されているが、多項式時間で計算可能なアルゴリズムは見つかっていない.与えられたゲームがどちらに有利であるかという判定問題はNP∩︀co-NPに入ることが知られている.本研究では、ある限定された単純確率ゲームの最適戦略を見つける難しさについて考えて、指数個ある戦略のうち、与えられた一つの戦略が最適かどうかの検証は多項式時間で計算可能であることを示した。さらにすべての最適戦略の複雑性について考察を行なった。一般的に解の存在の判定問題は多項式時間で計算可能でも、解の個数を数え上げることはかなり難しくなる問題が知られている。しかし今回驚くべきことに、このSSGでは最適戦略が実際に複数個になる場合があるにもかかわらず、データ構造をうまくとることによって、すべての最適戦略の記述を多項式サイズに収められることが証明できた。
- 社団法人電子情報通信学会の論文
- 1995-03-27
著者
関連論文
- On the zero-run length of a signed binary representation
- 出力VHDLコードに透かしを埋め込むCADツールの不正コピー検知方式
- ACM CCS2007会議ならびに併設ワークショップ参加報告(セッションA-5:法律と社会,報告)
- Information Security Conference (ISC)/International Workshop for Applied PKI (IWAP)/Secure Mobile Ad-hoc Networks and Sensors (MADNES)参加報告(セッション2)
- IT Forensicの研究開発動向 : アジア国際ワークショップ開催報告(セッション4-B:アクセスログ解析と報告)
- 公開鍵暗号基盤における匿名バイオメトリクスを用いた秘密鍵管理の提案
- ダークネット観測データに基づく攻撃挙動の特徴抽出に関する考察
- DynaAO:共有ライブラリとの接点に着目したAOPを用いたプログラムの振る舞い解析(セッション5-B:セキュアプロトコルとセキュアソフトウェア開発)
- DynaAO : 共有ライブラリとの接点に着目したAOPを用いたプログラムの振る舞い解析(セッション5-B:セキュアプロトコルとセキュアソフトウェア開発)
- パケット生存時間を用いた確率的パケットマーキングによるIPトレースバック手法の提案
- ACM CCS2008会議ならびに併設ワークショップ参加報告(セッション1-A:セキュアファイルシステムと報告)
- 第3者マシンとの連携による不正侵入検知モデルの提案
- 結託攻撃に耐性のある3分木型Subset Difference法
- ACM WISEC 2010会議参加報告 (情報通信システムセキュリティ)
- ACM WISEC 2010会議参加報告 (技術と社会・倫理)
- ACM WISEC 2010会議参加報告 (情報セキュリティ)
- 第2回PKI研究ワークショップ参加報告
- 中国語迷惑メールにおけるベイジアンフィルタの適用と評価(セッション3)
- ベイジアンフィルタリングを用いた迷惑メール対策における多言語環境でのコーパス分離手法の提案と評価(ネットワークセキュリティ, 多様な社会的責任を担うコンピュータセキュリティ技術)
- チャレンジ-レスポンスとベイジアンフィルタリングを併用した迷惑メール対策の提案(ネットワークセキュリティ)(プライバシを保護するコンピュータセキュリティ技術)
- チャレンジ-レスポンスとベイジアンフィルタの併用によるエラーメールを装った迷惑メールの検出精度の評価
- UC frameworkにおけるfunctionalityの合成について(情報通信基礎サブソサイエティ合同研究会)
- 2冪算における直接計算法を用いたマルチスカラー倍算の効率性評価
- XTRに対するサイドチャネル攻撃と効率的な対策方式
- XTRに対するサイドチャネル攻撃と致率的な対策方式
- 暗号に利用可能なモンゴメリ型楕円曲線の存在数に関する一考察(数論アルゴリズムとその応用,その1)
- 有限体F_上の超楕円曲線暗号のソフトウェア実装 (代数曲線とその応用論文小特集)
- 票数2の超楕円曲線暗号のソフトウエア実装
- 一般秘匿性ポリシの束モデル
- テキストと画像情報用いた画像スパムフィルタリングの設計と評価(セッションB-10:spam,フィルタリング)
- 第3者マシンとの連携による不正侵入検知モデルの提案
- 無線通信における物理レイヤ/MACレイヤへのDoS攻撃に耐性を有する整合フィルタを用いた符号化方式
- ACM CCS2007会議ならびに併設ワークショップ参加報告(セッションA-5:法律と社会,報告)
- IT Forensicの研究開発動向 : アジア国際ワークショップ開催報告(セッション4-B:アクセスログ解析と報告)
- ACM CCS2008会議ならびに併設ワークショップ参加報告(セッション1-A:セキュアファイルシステムと報告)
- 公開鍵暗号基盤における匿名バイオメトリクスを用いた秘密鍵管理の提案
- 公開鍵暗号基盤における匿名バイオメトリクスを用いた秘密鍵管理の提案
- 内容の類似性を用いたトラックバックスパム判別法の評価と考察
- ACM WISEC 2010会議参加報告
- 機器認証DRMシステムの設計
- 機器認証DRMシステムの設計
- デバイス固有値を用いた対称暗号技術によるIDベース暗号化方式の実現(情報通信基礎サブソサイエティ合同研究会)
- デバイス固有値を用いた対称暗号技術によるIDベース暗号化方式の実現(情報通信基礎サブソサイエティ合同研究会)
- デバイス固有値を用いた対称暗号技術によるIDベース暗号化方式の実現(情報通信基礎サブソサイエティ合同研究会)
- IPアドレスデータベースと確率的パケットマーキングを用いたパケットフィルタリング機構の設計
- IPアドレスデータベースと確率的パケットマーキングを用いたパケットフィルタリング機構の設計
- カオスベース画像スクランブル暗号への効果的攻撃(一般:情報通信基礎サブソサイエティ合同研究会)
- カオスベース画像スクランブル暗号への効果的攻撃(一般:情報通信基礎サブソサイエティ合同研究会)
- カオスベース画像スクランブル暗号への効果的攻撃(一般:情報通信基礎サブソサイエティ合同研究会)
- パケット生存時間を用いた確率的パケットマーキングによるIPトレースバック手法の提案
- パケット生存時間を用いた確率的パケットマーキングによるIPトレースバック手法の提案
- A-7-20 パストランジスタを用いたDES S-boxの実装評価
- 出力VHDLコードに透かしを埋め込むCADツールの不正コピー検知方式
- ネットワークトポロジを考慮した効率的なマルチキャスト暗号方式
- ネットワークトポロジを考慮した効率的なマルチキャスト暗号方式
- オンライン・ショッピングにおける民事的紛争解決に関する提案
- オンライン・ショッピングにおける民事的紛争解決に関する提案
- オンライン・ショッピングにおける民事的紛争解決に関する提案
- ACM CCS2009会議ならびに併設ワークショップ参加報告
- クラウドコンピューティングにおけるセキュリティ研究動向
- A-7-25 Security Problems in Existing Privacy-preserving K-means Clustering Schemes
- プライバシー保護した相関ルールマイニングに関する再考
- プライバシー保護した相関ルールマイニングに関する再考
- プライバシー保護した相関ルールマイニングに関する再考
- A-7-24 Privacy-Preserving Density Estimation-based Clustering via Random Data Perturbation
- システムコールの発行履歴が表す情報量の機微に基づく異常検知手法
- システムコールの発行履歴が表す情報量の機微に基づく異常検知手法
- システムコールの発行履歴が表す情報量の機微に基づく異常検知手法
- e-Forensics 2008参加報告
- 複数の機密画像を埋め込み可能なグラフタイプ視覚復号型秘密分散方式の拡張(21世紀のコンピュータセキュリティ技術)
- 属性情報開示における公平性について
- 著作権保護のためのウェーブレット変換を用いた電子透かし方式の安全性評価
- 周波数変換に基づいた電子透かし技術の画質評価に関して
- 個別アドレス発行によるメーリングリストへのスパムメール削減方式の提案と評価
- 内容の類似性を用いたトラックバックスパム判別
- パケットフィルタポリシーの安全性解析と対策(研究速報,通信技術の未来を拓く学生論文)
- デジタル署名標準・メッセージ回復型エルガマル署名に対する部分ブラインドプロトコルの設計と解析
- ロール・ポリシーに基づくドキュメントアクセス制御モデル
- 初期値を考慮した共通鍵暗号操作モードの証明可能安全性
- SudanのReed-Solomon符号復号アルゴリズムを使ったブロック暗号の補間攻撃
- ブロック暗号における秘密鍵の平文ブロックのマスクについて2-key XCBCによるMAC生成スキームの安全性
- ブロック暗号における秘密鍵の平文ブロックのマスクについて : 2-key XCBCによるMAC生成スキームの安全性
- 非周期的自己アフィンタイル貼りにおけるタイルの境界集合の構成と彩色
- DHCPによって管理されたセグメントに存在する未使用IPアドレスの監視手法
- 認証局と販売者の共謀攻撃に対して安全な匿名消費者-販売者透かし方式
- 認証局と販売者の共謀攻撃に対して安全な匿名消費者-販売者透かし方式
- 認証局に対する信頼仮定を排除した匿名販売者-消費者透かし方式
- プライバシー保護した分散的ドキュメントクラスタリング
- プライバシー保護した分散的ドキュメントクラスタリング
- 第2回PKI研究ワークショップ参加報告
- 第三者機関を利用したワンタイムIDシステムの設計,及び信用論理による安全性検証(セキュリティ,フォーマルアプローチ論文)
- TCPに対するポートスキャンの高速検知手法(セッション1-B : 侵入検知システム(1))
- IEEE802.11i 4 Way HandshakeプロトコルをDoS攻撃から保護する整合フィルタを用いた符号化方式
- セキュリティ対策の統合評価における個々の対策についての評価技法の提案
- IEEE802.11i 4 Way HandshakeプロトコルをDoS攻撃から保護する整合フィルタを用いた符号化方式
- セキュリティ対策の統合評価における個々の対策についての評価技法の提案
- 情報セキュリティ対策の評価技法についての考察
- オンライン先読みページングゲームにおける最適戦略の設計と解析(計算理論とその応用)
- kサーバ問題の一拡張とその最適戦略の計算複雑性
- オンライン k-server ゲームの計算複雑性(不確実性を含むシステムにおける最適化手法)