演習問題 5

演習問題 5
平成 27 年 5 月 18 日
計算の模倣
第二回ではチューリング機械の重要な性質である万能性について触れた．これは各機械
の行う手順を
プログラム
字列（算譜）として書き下しておき，それを或る一つの機械で解釈・実行
できるという性質である．ここではこれをより精密に細かい単位に
けて理解し，時間制
限を課したときの様子を取扱うために，計算を論理回路で表して考えることにする．
回路
入力数 k ，出力数 l の回路（論理回路）とは図 4 のように，入力変数 x1 ，…，xk と素子
¬（NOT），∧（AND），∨（OR）からなる閉路のない有向グラフをいう．この回路は入力
変数 x1 ，…，xk に割当てる真理値を与えると出力として l 個の真理値が決る．回路 C と
真偽値 b1 ，…，bk ∈ {0, 1} とが与えられたとき，入力 b1 ，…，bk に対する C の出力を答え
る問題 cEval を考える．但し回路は例えば次のような命令列の形で与えることにする．
• i = 1，…，k については，i 番目の命令は xi := input である．
x1 ❋
x2
x3
❋❋
①
✏✏ ✙
❋❋ ①①①
✙
①①❋❋❋
✏✏ ✏ ✙✙
①
❋❋
①
✙
! #①①
" !
✏✏ ✏ ✙✙
∧❈
∨
✏ ✙✙
❈❈
④
✏
④
✙
❈❈ ④④ !
!
✏✏ ✙✙
❈
④
!"#$
%&'(
%&'(
!"#$
✏
¬
④④❈❈ ¬ ✏✏
✙
④④ ❈❈❈
④
✙✙ ✙
! '④
& ! ✏✏
✙
∧✶
∨✶ ✏✏
✶✶
✶✏✏✶
✙✙ ✙
$✏ ✶✶
✶✶
✙
%&'(
!"#$
¬
✶✶
✶✶ ✙✙
④
✶( '④④④④
✶( %✙✙
∧✸
∧
✸✸
☛
✸✸
☛☛
✸✸ ☛☛☛
✸) *☛☛
∨ （出力）
図 4 入力数 3，出力数 1，大きさ 7 の回路の例（¬ 素子は大きさに数えない）
．
5-1
• i = k + 1，k + 2，…，n については，i 番目の命令は xi := a(bxj ∧ cxk ) の形で
ある．但し j ，k は i 未満の正整数であり，a，b，c の位置には ¬ を置くか否か選べ
る（∨ 素子は ∧ と ¬ を組合せて表せる）．最後の幾つかの変数が出力変数であり，
それには冒頭に output を記する．
例えば図 4 の回路は ∧ と ∨ の素子を左上から順に x4 ，x5 ，…と名づけて x1 := input，
x2 := input，x3 := input，x4 := x1 ∧ x2 ，x5 := ¬(¬x1 ∧ ¬x2 )，x6 := ¬x4 ∧ x5 ，
x7 := ¬(¬x4 ∧ x5 )，x8 := x6 ∧ ¬x3 ，x9 := x7 ∧ x3 ，output x10 := ¬(¬x8 ∧ ¬x9 ) と表
される．
このように与えられた回路は多項式時間で評価できる．すなわち cEval ∈ FP が成立
つ．これは命令列に従って各変数の値を順に求めればよいから明らかであろう．
計算の符号化
チューリング機械の動きを回路で表そう．ここでは簡単のため，出力テープを有せず，
第二回の脚 *3 のように受理状態 q終1 や拒否状態 q終0 への到達によって答を表す機械 M
を考えよう（以下「1 を／ 0 を出力する」と「受理／拒否する」を同じ意味で通用する）．
第二回の機械の定義で述べたように M は組 (Γ, , k, Q, q始 , q終1 , q終0 , δ) である．何らか
の入力 x を与えて動作させると，各時点の
• 機械の内部状態（Q の元）
• 入力テープ上の読取り位置
• 各作業テープ上の読取り位置
• 各作業テープに書かれた内容
が定まり，爾後の動作はこれ（と x）のみから決定する．この四つのものの組を時点表示と
呼ぶことにする．もし入力 x の長さが n ∈ N であり，M がやがて停止してその消費空
間（作業テープ上で訪れる枡目の個数）が s ∈ N 以内であるならば，このうち後三者はそ
れぞれ，n 以下の非負整数，s 未満の非負整数，Γ s の元（に
. . . が付いたもの）である
ので，時点表示は
ID M,n,s = Q × {0, . . . , n} × {0, . . . , s − 1}k × (Γ s )k
という有限集合の元となる．これは一定の長さ──具体的には O(log|Q|+log n+k log s+
ks log|Γ |) 程度──のビット列で表される情報である．
さて，時点表示 d ∈ ID M,n,s の次にどの d′ ∈ ID M,n,s へ遷移するか（d で既に停止して
いるときは
宜上 d′ = d としよう）は，x，d から機械的に単純な操作で決る．この「機
械的に決る」ということを正確に述べる言い方は幾つかあるが，ここでは (x, d) から d′
5-2
を求める回路が容易に作れることと考えることにする．すなわち次の問題 makeStep が
FP に属する．
入力
機械 M（を表す
出力
(x, d) ∈ Σ n × ID M,n,s（を表すビット列）を入力すると，その一遷移後の時点表示
字列）と羅列表記された整数 n，s との組 (M, 0n , 0s )．
d′ ∈ ID M,n,s を出力するような回路（図 5.1）．但しこの回路は，もしこの遷移によ
り消費空間が s を超える（d′ が ID M,n,s 中にない）ときは何を出力してもよい．
ここで M を表す
字列とは組 (Γ, , k, Q, q始 , q終1 , q終0 , δ) を適当に符号化したものであ
る．例えば遷移規則 δ は，δ(q, (γ入 , γ1 , . . . , γk )) = (q ′ , (γ1′ , . . . , γk′ ), (s入 , s1 , . . . , sk )) と
いう記述を各 (q, (γ入 , γ1 , . . . , γk )) ∈ Q \ {q終1 , q終0 } × Γ 1+k についてひたすら書並べる
ことによって表す．
実際，この回路が実現すべきは次のような手順である．
• 時点表示 d のうち機械の状態を表す部を取出す．
• 時点表示 d のうち各テープ上の注目点の位置を表す部を読み，に各テープの内
容を表す部
と x とを見ることで，機械が現在読取っている
字を知る．
• これらから遷移規則 δ に従って次の動きが決るので，それに d に施して新たな時点
表示 d′ を得る．
これを ¬，∧，∨ の素子のみを
った回路で実装するのは骨が折れるが機械的にできる単
純作業ではある．詳しく調べるとこの作業が (M, 0n , 0s ) を入力として多項式時間ででき
る，すなわち makeStep ∈ FP であることが確認できる．
この一回の遷移を表す回路を図 5.2 のごとく組合せると，指定した回数の遷移の繰返し
を表す回路が得られる．故に次の問題 makeCirc も FP に属する．
入力
出力
機械 M と羅列表記された整数 n，s，t との組 (M, 0n , 0s , 0t )．
字列 x を入力すると，M に x を入力して t 遷移後までに受理するとき 1，しな
いとき 0 を出力する回路．但しこの回路は，もしこの t 回の遷移をするうちに消費
空間が s を超えることがあるときは何を出力してもよい．
但し図 5.2 で
った init は計算開始時の時点表示（を出力する 0 入力の回路）であり，
isAcc は与えられた時点表示が受理状態にあるときのみ 1 を出力する回路である．いずれ
も n，s から容易に作ることができる．
問 5.1
5
次の判定問題 timeEval が P に属することを，makeCirc ∈ FP と cEval ∈ FP
から示せ．
入力
機械 M と
出力
M に x を入力すると時間 t 以内に受理するか．
字列 x と羅列表記された数 t ∈ N との組 (M, x, 0t )．
5-3
x
d
5.1
init
d
x
..
.
0
字列 x と時点表示 d とを与えると次
の時点表示 d′ を答える回路．与えられた組
(M, 0n , 0s ) に対し，機械 M の動きを表すこ
のような回路を作ること（makeStep）は
容易である．数 n，s はこの回路の寸法，す
なわち扱う入力 x と時点表示 d，d′ の大き
さを指定している．
問 5.2
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
;
t
1/0
5.2 図 5.1 の回路を t 個って作った回路．与
えられた組 (M, 0n , 0s , 0t ) からこの回路を作るこ
と（makeCirc）は容易である．
図5
8
isAcc
9
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
=
機械の動きを模倣する回路．
各 n ∈ N について回路 Cn を定めたもの (Cn )n∈N を回路族という．この回路族
が判定問題 A を解くとは，各 n ∈ N について Cn が n 入力 1 出力であり，長さ n の任意
の A の個例 x に対し，Cn に x を入力したときの出力が A(x) に等しいことをいう．回路
族 (Cn )n∈N が多項式時間構成可能であるとは，数 n ∈ N を羅列表記した
字列 0n が与
えられたときに Cn を求める問題が，FP に属することをいう．
判定問題が P に属するには，或る多項式時間構成可能な回路族によって解かれることが
必要十
であることを示せ（makeCirc ∈ FP や cEval ∈ FP を用いよ）．
5-4
対角線論法と階層定理
ここでは P に属しないが，P を含む級である
EXP =
!
k∈N
" k#
DTime 2n
（指数時間限定の機械で解かれる判定問題の全体）には属する問題 Dexp を構成しよう．つ
まり EXP \ P が空でないこと（P ! EXP という真の包含）を示そうというのである．
問 2.1 で計算不能な判定問題 D を作ったのと同様に再び図 3 の表を，しかし今度は縦
軸に並べるのを多項式時間限定の機械のみとして考える．Dexp をうまく定義していずれ
の行とも
い違うようにしたいわけだが，ここで Dexp ∈ EXP を成立たすのが聊か難し
い．というのも先のごとく「M に M を入力した結果」を調べて Dexp (M ) を定めたので
は，限られた時間で Dexp を計算できなくなってしまう．機械 M それぞれは多項式時間
限定だが，その多項式というのが M ごとにまちまちなので，Dexp を計算する時間を一
括りに抑える役には立たないのである．そこで M を「入力 M において」過たすという
方針は諦め，代りに「入力 (M, 0)，(M, 00)，(M, 000)，…のいずれかにおいて」過たせよ
う（或る入力で過てばよかったのだから，これで十
である）．Dexp を，機械 M と羅列
表記された数 k ∈ N の組 (M, 0 ) が与えられたとき，
k
M に (M, 0k ) を入力すると消費時間 2k 以内で受理しない
か判定する問題とする．
問 5.3
6＋5
（1）これで確かに Dexp ∈
/ P が成立つことを示せ．
（2）問 5.1 の timeEval ∈ P を
って Dexp ∈ EXP を示せ．
これで P ! EXP が示されたが，実は timeEval ∈ P のみならず timeEval(M, x, 0t )
の計算は O(|M | · (|x| + t) log(|x| + t)) 時間で
み，これを用いて
に議論を適切に精密
化すると，1 ≤ a < b なる任意の実数 a，b について DTime(na ) ! DTime(nb ) がわかる．
この P ! EXP や DTime(na ) ! DTime(nb ) のように資源の量を増やすと処理できる問題
が真に増えるという形の事実を
称して階層定理
（hierarchy theorem）という．
5-5
B
T (x)
T
A
x
A(x)
図 6 A から B への多対一帰着 T は，A の個例 x を，答が等しい B の個例 T (x) に変換するもの
である．それが多項式時間でできるとき A ≤Pm B と書く．
多対一帰着
或る問題が P などの級に属しないと証明するのは難しいことも多いが，二つの問題を比
べて相対的な困難さを調べることができる場合がある．
判定問題 A から判定問題 B への多対一帰着（many-one reduction）とは，函数 T で
あって任意の x について A(x) = B(T (x)) が成立つ*1 ものをいう（図 6）．そのような T
であって FP に属するものが存在するとき，A は B に多項式時間多対一帰着（カープ帰
着）するといい，A ≤P
m B と書く．
これは，A を解くにはその入力 x に函数 T を施して得られる T (x) を入力として B を
解けばよいと述べており，つまり（T を計算する手間を無視すると）「B が解ければ A が
解ける」「A の難しさは B 以下」と言える*2 ．実際もし B が P に属するならば，これと
T とを合せて解ける A も問 4.3 の議論により P に属する．ただ帰着の利はむしろ以下の
問のごとく B が P に属するか否か不明なときも相対的に二つの問題の難しさを比べられ
る所にある．講義では，
• 与えられた無向グラフ G と正整数 k とに対し，G に大きさ k 以下の点被覆がある
か判定する問題 vc
• 与えられた無向グラフ G と正整数 l とに対し，G に大きさ l 以上の独立集合がある
か判定する問題を is
*1
*2
A や B が約束つき問題（→「補足」）のときは，「任意の x ∈ dom A に対して T (x) ∈ dom B かつ
A(x) = B(T (x)) が成立つ」とする．
ただ，そのような意味をもつ比の仕方としては他にも考えられる．実際講義の後半では別の帰着を扱う
こともある．ここで多対一帰着をうのは，後に NP 完全性を論ずるときなどに都合が良いからである．
5-6
• 与えられた無向グラフ H と正整数 l とに対し，H が大きさ l 以上の閥をもつか判
定する問題を clq
が互いに多項式時間多対一帰着することを示し，これにより三者は皆が P に属するか，或
いは一つも属しないかであることを見た．なおそのいずれであるかは未解決である．
問 5.4
2＋9
問 4.5 の 2CNF 式や問題 2sat と同様に，三選言節の連言を 3CNF 式といい，与
えられた 3CNF 式が充足可能か判定する問題を 3sat という．また問 4.5 の直後にある
ように，与えられた命題論理式が充足可能か判定する問題を sat という．
与えられた回路が充足可能か（すなわち或る入力に対して 1 を出力するか）判定する問
題を cSat とする．
P
（1）3sat ≤P
m sat 及び sat ≤m cSat を示せ．
（2）cSat ≤P
m 3sat を示せ．
講義ではグラフに関する問題 vc，is，clq どうし，問 5.4 では論理式と論理回路に関す
る問題 3sat，sat，cSat どうしを比べ，それぞれ難しさの度合が或る意味で等しいのを
確かめたわけであるが，実は後の講義で明らかになるように，vc，is，clq と問 5.4 の問
題の間でも双方向に帰着する．このように一見かなり異なる手合の問題を比べられるのが
帰着という考え方の強みである．
問 5.5
1＋13
論理回路の ∧，∨ の代りに＋，× を
るものはなく，定数 0，1，−1 が
ったものを算術回路と呼ぼう．但し ¬ に当
える．またここでは出力数 1 の回路のみ考える．すな
わち入力数 k ，素子数 n の算術回路は次のように命令を並べたものである．
• i = 1，…，k については，i 番目の命令は xi := input である．
• i = k + 1，k + 2，…，n については，i 番目の命令は次のいずれかの形をしており，
それぞれ通常の意味を表す．
xi := c（但し c は 0 または 1 または -1）
xi := xj + xk （但し j ，k は i 未満の正整数）
xi := xj × xk （但し j ，k は i 未満の正整数）
最後の変数 xn には x1 ，…，xk の多項式で表されるものが来るが，これをこの算術回路の
表す多項式と呼ぶことにする．与えられた算術回路に対し，それが表す多項式が零である
か判定する問題を A とする．
特に入力数 0 の算術回路が表す多項式は単なる整数である．与えられた 0 入力の算術
回路に対し，それが表す数が 0 であるか判定する問題を A0 とする．
5-7
（1）「A0 を解くには論理回路の評価（cEval）と同じように単に順に実行すればよい．
故に A0 ∈ P」と言う人がいる．何が誤りか．
P
（2）A0 ≤P
m A は明らかである．A ≤m A0 を示せ．
この問 5.5 の問題 A，A0 も P に属するか否かは不明だが，一方が属するなら他方も属
することがわかったわけである．
問 5.6
16
約束つき判定問題 A と函数 g : N → N に対し約束つき判定問題 B を次で定める．
dom B = { x10g(|x|) : x ∈ dom A }
B(x10g(|x|) ) = A(x)
つまり B は A の「入力長を g の
(x ∈ dom A)
だけ水増しした」問題である．このとき（g によら
ず）B ≤P
m A が成立つことは明らかであるが，逆が成立つか考えよう．
A∈
/ P とし，g が超多項式的である（すなわち任意の k ∈ N について g(n) = Ω(nk )）と
する．このとき A ≤P
m B とはならないことを示せ．
注意
或る特定の帰着 T が FP に属せずというのみでは不十である．
ヒント「A から B への帰着を再帰的にって A を解く」
5-8

Download Report