【Books】Computational Complexity(Arora, Barak) Exercise Solutions
および、内容理解の手助けになりそうなことを。
問題番号 問題の概略
解答
文章中の「ヒント」とは、問題文の直後の補足、および巻末のヒントを指しています
Chapter 1
1.1
TMの定義が初めてならやる価値はあると思う
1.2 Languageは{0,1}でよいと示せ
発想:Mの構造の横に"2進の文字を読む機構"をつけて、一動作ごとにそれを噛ませる
1.3
本文にほとんど全部書いてある
1.4
これも上と同じく1stepを再現する計算量を気合いで調べる
これなんですが、Alphabetを$ \Gamma \times \Gamma \times \dots \times \Gammaってして1cellの中にkcell(とヘッドの位置情報)を詰めこむというアホみたいな証明が存在する これをするとヘッド移動の手間がなくなるので$ O(T(n))でいけてしまう
1.5
Claim1.6の本文中の証明と似たTMを作る, headの動きが行って戻ってをくり返し. 行きでtransitionを確認,帰りで実装する.これはinput lengthにしか依存しない. この計算量はもとのTMの1stepが最大$ 2T(n)かかるので$ O(T(n)^2). 2テープしか使わないのはかなり明らかでは
1.6 まずThm1.9のsingle-tapeの証明をしないといけない. $ TlogTっていうのは1stepあたり$ logT時間かかるってことだが,この$ logTってのは{0,1}でMの文字を表現するために生じる時間. この証明のマジックはつねにheadの近くにMのdescription(定数長さ)を置いておくこと(1stepでdescriptionの移動にC時間消費するが,これは誤差). これでuniversal TMの証明が終わっている.
これがobliviousになることをいえばよく, あれ?
Chapter 2
NPとcoNPが違うことがちゃんと言えるなら問題ないと思う SATの証明はかしこいなと思ってればいい
2.1 NPのdefで、certificateのlengthをequal ではなく at mostにしても大丈夫だといえ
length: p(|x|)+1を新たなpとする.$ 2^nを1からkまで足したのと$ 2^{k+1}-1は等しい.
2.2 2COL/3COL/Connectivityの判定 はNPといえ
2col 3colのcertificateは明らかで, 判定もpoly-time. connectivityはunion-findで検索
Pに入るのは2col. 塗れるのならば連結成分ごとに一意(連鎖的に定まる). これはpoly-timeで塗れる(二分グラフで検索) 矛盾したら弾けばよい.
2.3 有理n変数線形連立多項式はPに入るといえ
NPに入ること: ceritificate:変数の値
Pに入ること: Aを上三角行列にする. 掃き出し法は高々poly-time. 終わったら下から順番にO(1)で定まる
2.4 Linnear Programming はNPに入ると言え. Pに入るのは非自明なので調べて.
certificate: 変数の値
2.5 primeの判定がNPといえ
書いてあることそのまま
2.6 NTMのuniversalTMが存在すると示せ
(a) $ \alpha,xに対して,$ \alphaの表すNTMが$ xで$ T時間で止まるのなら$ C \left( \alpha\right)TlogTstepで止まるuniv. NTMが存在するといえ
(b) $ C \left( \alpha\right)Tstepでいえ.
2.7 thm2.8を補完せよ
by def.
2.8 HALTのNP-hard性をいえ. これはNP-completeか?
そもそもcomputableじゃないのにNPに入る訳ないので後半はno.
3-SATを次のように変換する.$ \varphiを3-CNF formulaとして, 3-CNF formulaに対してすべてのinputを試し,satisfying assignmentが見つかれば停止,最後までやったらもう一度最初からやるTMと$ \varphiを返す
2.9 poly-time Karp reducibilityのtransitivityをいえ
明らか(だよな……?)
2.10 $ L_1, L_2がNPに入るとき, $ L_1 \cap L_2, L_1 \cup L_1はどうか
certificateを次で指定する.
ひとつめ: <$ xが$ L_1に入るcertificate , $ xが$ L_2に入るcertificate>
ふたつめ: <$ i, $ xが$ L_iに入るcertificate>
TMはこれにあわせて適当に構成すればよい
2.11 ある命題がZF上n stepで証明可能か判定する問題はNP-completeといえ
certificate : 証明
3SATからの帰着 : or andの演算は0,1の掛け算などで表されるので,それの形に記述すればよい
2.12
中略
2.23 P$ \subseteq NP$ \cap coNP
Pに入っているならNPに入っている. coP=PからPに入っているならcoNPに入っている.
2.24 def2.19 def2.20が同一であると示せ
2.19の方が小さいこと: complementがNPに入っているとき, それを判定するDTM Mの出力を反転することで求めるTMとなる
2.20の方が小さいこと: 同じくTMの出力を反転させることで, complementに対して $ \exist uなら1を出力するTMが得られる
2.25 If P=NP then NP=coNP
P = coPより明らか
2.26 NP=coNP iff 3SATとTAUTOLOGYが互いにpoly-time reducible
お互いNP-complete, coNP-completeなので両方向ともに明らか.
2.27 NEXPのdefをNTMを用いずに与え,さらに等値性をいえ
certificateの長さについて, exponentialなものを許すことに注意. それ以外は全部同じ
2.28
2.30 unary($ 1^iという形の元だけからなる)なLanguage であってNP-completeなものが存在すればP=NP
unary language がNPに入るなら
Chapter3
3.1 {M | M runs in f(n)-time}が決定不可能
TMに関するPropertyなので.
3.2 $ \bold{SPACE}(n) \neq \bold{NP}を示せ
メモリを$ n^2くらい必要とする問題が本質的(逆方向はOpen Problemなはず).
それこそ「(多項式時間で停止する)TM, inputの組であってメモリ量$ n^2以内で動くかどうか判定せよ」など.
3.3$ B \in \bold{EXP} であって$ \bold{NP}^B \neq \bold{P}^Bであるものの存在を示せ
……?
3.5
3.9 $ Cをすべての語を1/2の確率で含むようにして定めたlanguageとする. 高い確率(Lebesgue測度0)で$ \bold{NP}^C \neq \bold{P}^Cとなることを示せ
$ \bold{NP}\cap Cは確実に$ \bold{NP}^Cに含まれる一方で, これが$ \bold{P}^Cに含まれるには$ Cが極めて強く偏る必要がある.
Chapter 8
死ぬほど大事なのでちゃんと読んだ方がいい IP/MA/AMの定義をちゃんと理解に落とし込んでおいたほうがいい
dIPとIPがなんでこんなに違うのか説明できたほうがいい
Chapter 9
おまけ程度の内容なので、まあ飛ばしてもいい
Chapter 10
10.6
素直に全通り考える
10.9
そもそもaに対して{y | a$ \odoty = 0}という{0,1}上のvector spaceはuniqueに定まる. これはa$ \neq0ならかならずdimがn-1.
よってa is unique $ \Leftrightarrow 得られた$ y_iたちで張られるvector spaceのdimがn-1$ \Leftrightarrow $ y_iたちが{0,1}上でindependent
この確率は$ \frac{1}{2} \cdot \frac{3}{4} \cdot \frac{7}{8} \cdot \frac{15}{16}\cdot\ \dots \ \cdot \frac{n^2-1}{n^2}
Eulerの五角数定理につっこむと収束先は十分大きい
10.10
繰り返し二乗法で検索
10.11
図を書くと自明 等分してるので。
10.12
ヒントがほぼ答え
Chapter 11
8章からさらに一般化された内容 大事です
証明が書かれていないやつ(11.5とか)は到底思いつけないやつなので次に行った方がいい 案外ちょっと後(or Chapter22)とかに書いてあるので、悩むより次に行く方がよい
かしこい証明などが多いが理解に戸惑うようなものは少ない
11.1 PCP(r,q)のSoundness propertyは$ \frac{1}{3}でなくてよく,任意であると示せ
ここまで散々やった 何回もやるだけ
11.2 adaptiveでr times randomness, q queries を投げるならnon-adaptiveでr times randomenss $ 2^qqueries でよいと示せ
L固定, adaptiveなVerifierをとってきて、q queriesの投げ方は2^q通り(各queryで何が返ってくるかで分岐)をすべて試す
11.5 Lem11.16を示せ
2章を見る
11.6 P=PCP(0,log(n))とNP = PCP(0,poly(n))
どちらも片側の包含関係は明らか. PおよびNPの方がでかいことが非自明. VerifierはRandomnessを扱えないことからRandomAccessは完全にxに依存し,xごとに一意になる. ここから任意の$ x, \piに対して$ Pr(V(x,\pi)=1) = 1 \ or\ 0が導ける. これさえわかれば両方とも明らか
11.7 L = {<A,k> | perm(A)=k}としたとき, LはPCP(poly(n),poly(n))に入ると示せ
?
11.10 J-PCP(log(n)) $ \subseteq L
Lはlog(n)個の乱数、およびO(r(n)) lengthのproofをすべて試せる
11.11 fをL(NP-language)から3SATへの(Chapter2で与えた)poly-time-reductionとし,このときあるxでf(x)は3CNF-formulaとしてclauseの数をmとし,m(1-o(1))個がsatisfiableであるようなものがあるといえ
空集合は除外する. 最初の1bitを反転すると受理されるようなものは常に存在する. tableauを3-CNF formulaに直す工程を考えれば,これは1個以外すべてsatisfiable.
11.13 poly-time TMであって, 2CSP-instanceへのsatisfying assignmentを出力するものを構成せよ
依存関係をgraphにおこす. さらにx=1ならy=1(あるいは0なら0)という関係ならx,yはつぶして一つの頂点とする.すると2colの問題になるので,2col is in Pよりあとはdownward reductionでassignmentを出すだけ.
11.15 QUADEQ is NP-complete
NPに入るのは明らか. 3CNFのclauseに対して, たぶん気合いでなんとかなる.はず.
11.16 Q係数線形連立多項式の maximal satisfiable equationsを見つける問題について,$ \exist \rho, \rho以上のapproximationを要求するのならNP-hard
MAX-3SATからの帰着は明らか.この帰着から11.15を考えてさらに$ F_2の場合でもよい.
Chapter 12
かなり面白いです, おすすめ. 別に前をそこまで読んでなくても読める
本文中にtypoが多いです 自分の心を信じた方がいい
12.1 $ f:\{0,1 \}^n \to \{0,1\}はすべての$ iについてある$ xが存在し, $ f(x) \neq f(x^i)とする. ただし$ x^iは$ xの$ ibit目のflipである.このとき$ s(f)は$ log(n)以上のorderをもつと示せ
?
12.2 $ \forall k \in \mathbb{N}, $ f_k :\{0,1\}^{2^k} \to {0,1}をAND-OR funcとする. $ D(f_k) =2^kを示せ.
induction. k=1で明らか, n-1までよいとしてこのとき最後の1stepは両方を計算すればそれで判明しているはず.
12.3 $ f:\{0,1\}^{k^2} \to \{0,1\}であって, これはk個のdisjointなORのANDであるとする. 以下すべてを示せ : $ s(f)=bs(f)=C(f)= \sqrt{n}=k,\ deg(f)=D(f)=n, \ R(f) \geq \Omega(n)
$ k \leq s(f): $ (1, \dots,1,0,\dots 0)(最後のk個だけ0)について, last k bitsがfliperに数えられる.
$ s(f) \leq bs(f) : 一般に成立する
$ bs(f) \leq k : outputが0のとき. 少なくともあるORが0で, outputを変えるにはこのk-bitsのどれかをflipする必要がある.よってblock分けは最大でもk個.
$ D(f)=n : 構成は目に浮かぶと思います.
$ deg(f)=n : そのままOR($ 1 - \prod_ix_i)とAND($ \prod_ix_i)の式にぶち込んで, 展開すると次数は自明にn.
$ R(f) \geq \Omega(n) : Min-Max-Lemmaより求めるは, $ \max_D\min_A cost(A,D).$ Dを次で定める : $ (0,\dots,0,1,0,\dots,0)という形の, どこか一つだけ1のあるk-bitsの列がk個連なったものの全体を$ D'として, $ D = \{x^i|x \in D' ,\ i\in \{1, \dots ,n\}\} \cup D', ただし$ x^iは$ xの$ i番目の1を0にflipしたものとする.
これの判別をしようとすると, $ D'とそうでないものの判別をすることになるが, $ \frac{k}{k+1}で$ D'でない元を引くことになり, そのとき"当たり"のk個の組を引くのに$ \frac{k}{2}個の組を(Expected-timeで)試す必要があり, かつそこまでの各組で1を引くのに同じく$ \frac{k}{2}個のbitを(Expected-timeで)調べる必要がある. よって期待所要時間は最低でも$ nの定数倍以上となる.
12.4 これ多分問題文がtypoで意味が読み取れません. 3rd.edを持っている人誰か教えて
12.5 fに対して, それを表現するmulti-linear polynomial : pはuniqueであると示せ
同値命題 : multi-linear polynomial : pについて,$ \{0,1\}^nのすべてのinputで0になるのならそれは0である.
これは明らかである. multi-linearなので仮定からあらゆるassignmentで0, これは恒等的に0.
12.6 PARITY(1が偶数個なら1, 奇数個なら0)のpolynomialを求めよ
2変数XORを考える, あとはそれをつなげる. 一意性より明らか.
12.7 $ deg(f) \leq D(f)を示せ
$ D(f)を実現するTree : $ tを考える. $ tのrootからleafまでのすべての(validな)pathであって1で終わるものについて, そのpathを通るのに必要な変数条件を掛け算で繋げた項を作って, それらの和を取った多項式を考える. これが$ fを計算していることは明らか. またこの次数は明らかに$ D(f)以下である. 一意性からこれでよい.
Chapter13