Document

交替性計算の
潜在的能力
豊橋技術科学大学
知識情報工学系
相田慎
科学研究費補助金若手研究(B) 21700012 「交替性計算の潜在的能力」
いろいろ（この発表だけ、浮いてない?）
新しい結果の話は特にない（残念）。
 具体的なゲームの話もあまりしない。
 「交替性計算」は、その能力が発揮されていな
いと感じている（これが一番言いたいこと）。
 今考えていることをお話して、賢明な皆様の
お智慧をお借りしたい。
 発表するのは初めてですが、この研究集会は
今回含めて4回参加（地味）

2010/3/1
交替性計算の潜在的能力
2
発表の流れ
「交替性計算」とは何哉?
「決定性計算」と「交替性計算」
1.
2.

決定計算量の特徴付け定理[Chandra-KozenStockmeyer]と神託分離定理[Orponen]など
「非決定性計算」と「交替性計算」
交替性計算における「唯一性」とは?
3.
4.

5.
2010/3/1
昔考えたことの紹介
「交替性計算」に「潜在的能力」はあるのか?
交替性計算の潜在的能力
3
交替性計算とは何哉
「交替性計算」とは何哉(1/2)

「非決定性計算」の自然な拡張
 計算木の接点に
and/or （∀/∃）が「交互に」
ラベル付けされている
∨
∃
∀
∨
∧
∀
∨
∧
∨
∃
∀
∨
∧
2010/3/1
∨
∃
∀
∨
∧
∀
∨
∧
∨
∃
∨
∃
∀
∨
∧
∀
∨
∧
交替性計算の潜在的能力
∀
∨
∧
∀
∨
∧
∀
∨
∧
5
「交替性計算」とは何哉(2/2)

二人ゲームの必勝性判定問題と捉えても良い
∨
∃
∀
∨
∧
∃
2010/3/1
∨
∃
∀
∨
∧
∃
∀
∀
∨
∧
∃
∃
: 先手
∀
: 後手
∀
∨
∧
∨
∃
∀
∨
∧
∃
∀
∨
∧
∃
∃
∨
∃
∨
∃
∀
∨
∧
∀
∃
∀
∨
∧
∃
∀
交替性計算の潜在的能力
∀
∨
∧
∃
∃
∀
∨
∧
∃
∃
∀
6
「決定性計算」と
「交替性計算」
「決定性計算」と「交替性計算」
次の結果が有名:
 [Chandra-Stockmeyer 1976] a)
 [Chandra-Kozen-Stockmeyer 1981] b)
 「Savitch
の定理」の交替性計算版(?)
 決定性計算に交替性計算の上下界を与える
 具体的内容は次ページ
a. Alternation. Proc. 17th 1EEE Symp. on FOCS, pp.98-108, 1976.
b. Alternation, Journal of the ACM, Volume 28, Issue 1, pp. 114-133, 1981.
2010/3/1
交替性計算の潜在的能力
8
Chandra-Kozen-Stockmeyer（1981）

「決定性計算」の「交替性計算」による特徴付け



系



2010/3/1
交替性計算の潜在的能力
9
Chandra-Kozen-Stockmeyer(直観)

長い決定性計算線を交替性計算木へ対数圧縮
（時空間の変換）
時間を圧縮
並列計算を時間に伸長
2010/3/1
交替性計算の潜在的能力
10
「交替性計算」の側面

三つの側面
1.
実用的な並列計算（ハードウェア実装可能性）

2.
計算困難性の証明道具


3.
還元ガジェット用
理論的だが非実用的（3QBF-SAT など）
回路の動的生成機


2010/3/1
NC ～ NL ～ P完全「未満」問題向け
「計算木」はトップダウン生成された回路と見做せる
回路計算量との関係性
交替性計算の潜在的能力
11
「非決定性計算」と
「交替性計算」
指数時間仮説と交替性

仮説: 3SAT は決定性
3SATの非決定性計算木
-時間で解けない
3QFB-SATの交替性計算木
深さ
幅
幅
疎（スカスカ）
問題が違うのに、どちらも決定性
2010/3/1
交替性計算の潜在的能力
密（ミッチリ）
-時間で計算可能
13
「非決定性計算」と「交替性計算」

自明な包含関係しかわかっていない:
や
のようなクラスとの関係も未知
 相対世界上でなら包含関係がわかるのでは?
⇒ [Orponen 1983] の奇妙な結果（次ページ）

Complexity Classes of Alternating Machines with Oracles. ICALP 1983 : 573-584
2010/3/1
交替性計算の潜在的能力
14
Orponen (1983)

次を満たす帰納的神託
を構成できる:
← こちらを概説します
 注意:
2010/3/1
以下は成り立つ（再掲）
交替性計算の潜在的能力
15
Orponen(1983)のアイデア
1.
次のような集合を定義する:
2.
の証明のように、神託を
短い語から積み重ねて構成する。
は神託に問い合せる
だけなので自明。
を対角線論法で示す。 □
3.
2010/3/1
交替性計算の潜在的能力
16
Orponen(1983)の示唆
指数時間で問い合わせ可能でも、「多項式」
という限られた領域では問い合わせできない
ような神託を構成しただけか?
 No （おそらく）: 交替性計算では、

 決定性時間・領域を
対数的に圧縮する。
 その代わりに、並列計算の幅が広がる。
 「交替性計算木を評価することが計算の本質」で
あるような問題があるのではないか?
2010/3/1
交替性計算の潜在的能力
17
交替性計算における
「唯一性」とは
唯一性: 非決定性計算の概念の拡張

唯一性（無曖昧性）
2010/3/1
NP （UP）計算では
AP計算では
証拠は一つ
先手が唯一の必勝手を選択すれば
後手がどんな手を選択しても
先手が唯一の必勝手を選択すれば
後手がどんな手を選択しても（以下略）
交替性計算の潜在的能力
19
「強唯一性」と「全唯一性」
([Aida-Crasmaru-Regan-Watanabe 2002]の話題について)

二種類の「唯一性」を定義
 強唯一性(Strong Uniqueness Property)
 定義（概要）: 必勝法を持つ側は、各局面において唯一の必勝手
を指さなければ勝てない
 全唯一性(Global Uniqueness Property)
 定義（概要）: 強唯一性必勝法を持つ側が、必勝手を打ち続けな
ければ、相手が強唯一性必勝法を持つ
動機: 一般化詰将棋問題を余詰無しにできないか?
⇒ 「強唯一性」を持つゲームを詰将棋ガジェットとして
埋め込めれば十分

2010/3/1
交替性計算の潜在的能力
20
「強唯一性」をどう実現するか?




ゲームのルールに「相手と立場が変われる」選択肢
があると嬉しい。
ただし、制限が無いと無限ループに陥る（当然）。
羽生名人も子供の頃、優勢盤面をひっくり返して、
わざと劣勢にして遊んだらしい（Wikipedia より）。
既存のゲームに「先手後手交換」の挑戦権（次ペー
ジ）を加えたゲームを構成してみよう。
2010/3/1
交替性計算の潜在的能力
21
挑戦法(Challenging)のラフなアイデア

相手が打った必勝手以外に良い手があったら、
「待った」と言って盤面を引っくり返し、自分が
「その（別の）必勝手」を打つ。
←こうなる感じ?（実世界）
←これが
© トムス・エンタテインメント
2010/3/1
交替性計算の潜在的能力
22
閑話休題。
2010/3/1
交替性計算の潜在的能力
23
挑戦法に基づいて二人ゲームを用いた
強唯一性ゲームの構成法
1.
2.
相手が指した必勝手以外の良い手があったら、
「待った」と言って先手・後手の立場を入れ替え、自分
が「より左の手」を指す（左の手がない場合は負けと
定義する）。
必勝手を持つ側が勝つためには:


3.
どの盤面でも相手に「切り札」を使われないように、（唯一
の）最左必勝手を指せば良い。
最左手以外の手を指した場合、優位性が逆転する（この証
明に「交替性」を用いる）。
挑戦法ルールを追加すれば、任意のゲームを強唯一
性ゲームにできる。 □
2010/3/1
交替性計算の潜在的能力
24
全唯一性(1/2)

（再掲）強唯一性必勝法を持つ側が、必勝手を打ち
続けなければ、相手が強唯一性必勝法を持つ
∨
∃
∀
∨
∧
∀
∨
∧
∨
∃
∀
∨
∧
∃
2010/3/1
∨
∃
∀
∨
∧
∃
∀
∀
∨
∧
∃
∃
∀
∨
∧
∃
∃
∨
∃
∨
∃
∀
∨
∧
∀
∃
∀
∨
∧
∀
∀
交替性計算の潜在的能力
∀
∨
∧
∃
∃
∀
∨
∧
∃
∃
∀
25
全唯一性(2/2)


完全二分木で木の深さがわかっていれば限定すれ
ば、（実は）受理状態数と拒否状態数の数が一意に
求まる。
同じ深さの完全二分木において、
 受理木になる場合の受理状態数
 拒否木になる場合の受理状態数

の差は必ず 2 になる。
（i.e. 計数計算クラス SPP に入る）
深さ同一の全唯一性計算木ならば、葉の状態ラベ
ルによらず同型（∵ 木の深さに関する帰納法）。
2010/3/1
交替性計算の潜在的能力
26
「交替性計算」に
「潜在的能力」は
あるのか?
「交替性計算」をどう応用する?

NP/co-NP完全問題を特徴付ける（のは多分
難しい……）
 NP∩co-NP
に属す問題ではどうか?（双対性）
「問題を解くこと」を「二人ゲームの必勝性を
解くこと」に置き換える
 「二人ゲームの妥当なルール」策定が肝心

 盤面サイズ:
交替性計算の領域
 最大手数: 交替性計算の時間
2010/3/1
交替性計算の潜在的能力
28
NP問題への応用(1/2)


二人のプレイヤの能力は無制限
共用する盤面の情報を交互に書き換える
^∃^
^∀^
: 盤面の書き換え情報
盤面
2010/3/1
ε（盤面サイズはあまり大きすぎないよ
うに構成する）
交替性計算の潜在的能力
29
NP問題への応用(2/2)

サイズ n の問題を二人ゲームに置き換え評価する

ならば
決定性時間で
計算可能（[Chandra-Kozen-Stockmeyer] より）

ならば
決定性時間で
計算可能（同上）

多項式より真に小さい関数領域で盤面を抑えられれ
ば、特徴づけ定理より、
 擬多項式時間や準指数時間で計算できる。
 計算時間を少し犠牲にして厳密アプローチで問題を解く。
 ルール（プロトコル）策定の枠組みがわかれば……
2010/3/1
交替性計算の潜在的能力
30
まとめ

交替性計算は決定性計算を（ある意味）圧縮
 神託分離定理が計算圧縮性を示唆

「唯一性」を交替性計算に適用する
 強唯一性:
「余詰無し詰将棋」などに有用
 全唯一性: 「唯一性」の意味によって、
交替性問題を計数問題へ変換する

交替性計算に（未知の）潜在的能力があるか?
など非決定性計算との関係が未知
 二人ゲームの効率的プロトコルを作れれば……
 NP
2010/3/1
交替性計算の潜在的能力
31
余談
「交替性計算」なんて古いんじゃない?

乱択や量子などを使わない古典計算モデル
で事実上最も強力な計算モデル
 計算木の各節点が加法やガロア体などにしても、
交替性計算に還元可能
NP との関係性など、実は残っている問題が
多そう（「落穂拾い的」なものであっても、研究
する意義はある）
 「温故知新」

2010/3/1
交替性計算の潜在的能力
33

Download Report