一般化詰将棋問題の指数時間完全性について
スポンサーリンク
概要
- 論文の詳細を見る
縦横nマスに将棋の盤面を拡張し, その盤面上で詰将棋が与えられる.この詰将棋が詰むかどうかを決定する問題を, 一般化詰将棋問題と呼ぶ.本稿では一般化詰将棋問題が指数時間完全であることを証明する.一般化詰将棋問題の指数時間困難さの証明はG_3を利用する.G_3はすでに指数時間完全であることが知られている問題である(Provably difficult combinatorial games, SIAM J.Comput.8, 1979)
- 社団法人電子情報通信学会の論文
- 2000-10-20
著者
-
横田 雅也
名古屋大学大学院人間情報学研究科
-
築地 立家
名古屋大学大学院
-
築地 立家
名古屋大学人間情報学研究科
-
築地 立家
名古屋大学情報文化学部自然情報学科
-
岩田 茂樹
電気通信大学情報工学科
-
北川 智博
電気通信大学電気通信学部情報工学科
-
諸橋 玄武
電気通信大学電気通信学部情報工学科
-
北川 智博
電気通信大学情報工学科
-
岩田 茂樹
電気通信大学大学院情報理工学研究科情報・通信工学専攻
関連論文
- 量子オラクルを用いた唯一最短格子ベクトル問題の効率的解法
- 平面グラフのC^^-_7彩色問題の計算複雑さ
- D-1-2 「ストーンヘンジ」の先手必勝性と一般化ストーンへンジのPSPACE完全性(D-1. コンピュテーション,一般セッション)
- 平均次数の高いVC-PMの近似アルゴリズム (計算機科学基礎理論の新展開)
- 一様分布上での関係変数の量子学習
- 一般化された対称動作をするラングトンの蟻問題のPSPACE完全性
- 連続王手制限付き一般化チェス問題の指数時間完全性
- 唯一の必勝法を持つ二人ゲームの複雑さ
- 一般化詰将棋問題の指数時間完全性
- 手数制限付き一般化詰め将棋のPSPACE完全性について(LAシンポジウム(情報基礎理論ワークショップ)論文小特集)
- O(log n)長の単調単項式の負例学習について(LAシンポジウム(情報基礎理論ワークショップ)論文小特集)
- 一般化詰将棋問題の指数時間完全性について
- 一般化詰め将棋のPSPACE困難性について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
- 平均時計算量における2-tt還元とmany-one還元の違いについて (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
- $O(\log n)$長の単調単項式の負例学習について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
- 一方向性関数の平均時間計算量解析
- A note on lower bounds on constant-depth modular circuits
- Learning DNF by Approximating Inclusion-Exclusion Formulae (Models of Computation and Algorithms)
- 和集合のサイズの近似評価を用いたDNF式の学習について
- オンライン投資問題 (計算機科学基礎理論の新展開)
- On the Depth of Randomly Generated Circuits
- 回路計算量における和算と乗算のある違いについて
- D-1-1 一般化美術館問題のNP完全性(D-1.コンピュテーション,一般講演)
- 単一2負項を加えたホーン関数
- 単一2負項を加えたホーン関数
- 一般化ブロックパズルのPSPACE完全性の別証明 (計算機科学基礎理論の新展開)
- LAシンポジウム(計算機科学基礎理論ワークショップ)論文小特集の発行にあたって(LAシンポジウム(計算機科学基礎理論ワークショップ)論文小特集)
- LAシンポジウム(情報基礎理論ワークショップ)論文小特集の発行にあたって(和文論文誌D-I・英文論文誌E-D合同)
- T(G)を計算する新しいアルゴリズム
- T(G)を計算する新しいアルゴリズム
- (4,7)-、(5,6)-マージングネットワークの最小比較器数のコンピュータによる計算 (離散的アルゴリズムと計算量)
- (4, 7)-マージングネットワークと(5, 6)-マージングネットワークの最小比較器数について
- マージングネットワークの下界について
- マージングネットワークの下界の計算について
- マージングネットワークにおけるある下界について(計算量理論の諸相 : その基礎的研究)
- n×n盤面上の将棋の指数時間完全性について
- A-009 上書きハッシュ表の性質(A分野:モデル・アルゴリズム・プログラミング,一般論文)