計算量理論のバックアップ(No.16)

講義日程-2007年度冬学期

計算量理論(Computational Complexity) †

担当：今井浩教授
1.5単位
- 数理：限定選択B
10:15～11:45 理学部７号館(化学教育東館)236号室
参考書
- Michael R. Garey and David S. Johnson
  Computers and Intractability
  A Guide to the Theory of NP-Completeness
  W.H.Freeman and Co. NY. 1979

↑

過去問 †

とかないのかなぁ…isのwikiがみつからない。ないのかなぁ
今井桂子さんは奥さんですか？

ここにあります．

↑

予想問題 †

Presented by yambi. tzik all blame reserved.
（誰か何が出ると言っていたか知っている人は教えてください．yambiは授業に出てません．）
誤植は見つけた人が直してね

0-1ナップザック問題とは
- Instance 非負整数 $v_1,v_2,\dots,v_n, w_1,w_2,\dots,v_n, W$
- Task $\sum_{i\in S}w_i\le W$ を満たし $\sum_{i\in S}v_i$ を最大化するような $S\subset \{1,\dots ,n\}$ を求める．
PARTITION問題とは
- Instance 非負整数 $a_1,a_2,\dots ,a_n$
- Task $\sum_{i\in J}a_i=\sum_{i\in I\setminus J}$ なる $J\subset \{1,2,\dots ,n\}=I$ は存在するか？
- PARTITIONはNP-complete
  SAT $\le^{\mathcal{P}}$ 3SAT $\le^{\mathcal{P}}$ 3DM $\le^{\mathcal{P}}$ PARTITION と示せる．
  具体的な証明はhttp://tzik.homeunix.net/yambi/files/computation.pdfとか．
  あんまり信用しない方がいいけど．
0-1Knapsack問題のNP-hard性．
- PARTITION問題から多項式帰着する．
- PARTITION問題のInstance $a_1,a_2,\dots ,a_n$ が与えられたとき， $v_1=a_1, v_2=a_2, \dots ,v_n=a_n, w_1=a_1,w_2=a_2,\dots ,w_n=a_n, W=\sum_{i\in\{1,2,\dots ,n\}}a_i/2$ とする．
- このとき $\sum_{i\in S}v_i$ の最大値が $\sum_{i\in\{1,2,\dots ,n\}}a_i/2$ であるかどうかが分かればPARTITION問題が解ける．
- この変換が多項式帰着であることは明らかなので0-1Knapsack問題はNP-hard
擬多項式時間アルゴリズム
- 動的計画法を用いる．ただし，表の範囲外を参照されたら0を返すことにする．
- $x(j,k)$ を $\sum_{i\in S}v_i=k$ となるものの中での $\sum_{i\in S}w_i\le W$ の最小値とする．ただし $S\subset\{1,2,\dots ,j\}$ とする．
- このとき，表の埋め方は $c_j\le k$ かつ $x(j-1,k-v_j)+w_j\le \min\{W,x(j-1,k)\}$ のときは $x(j-1,k-v_j)+w_j$ ，それ以外のときは $x(j-1,k)$ を埋めていく．
- $x(n,k)$ を走査すれば，何が選ばれたのかが分かる．
- 計算時間は $C$ を最適解の値の上界として $nC$ ．例えば $C=\sum_{i=1}^n v_i$ とできるが，これは擬多項式時間アルゴリズムである．
KNAPSACK問題の $1/2$ 近似アルゴリズム．
- アルゴリズム
  $\frac{v_1}{w_1}\ge\frac{v_2}{w_2}\ge\dots\ge\frac{v_n}{w_n}$
  を降順にソートし大きいものから順に $w_i\le W$ を満たすものを取り出し，
  $(v_1',w_1'),(v_2',w_2'),\dots ,(v_n',w_n')$
  とする．ここで，整数 $k$ を
  $k=\min\left\{j\in\{1,2,\dots,n\}\left|\sum_{i=1}^j w_i'>W\right.\right}$
  と定義する．このとき， $\{1,2,\dots,k-1\}$ と $\{k\}$ のうちより良い方の解を選ぶ．（どちらも実行可能解であることに注意．）
- 計算時間
  ソートにかかる時間 $O(n\log n)$ ，条件を満たす $k$ を求めるために $O(n)$ かかるので，合わせて $O(n\log n)$ である．多項式時間．
- 近似値比
  $\{1,2,\dots,k-1\}$ と $\{k\}$ の二つの解の和は明らかに最適解以上のものとなっているので，近似値比は $1/2$ である．
KNAPSACK問題はFPTASである．
- $1-\varepsilon$ 近似値比アルゴリズムが存在することを示せばよい．
- 具体的なアルゴリズム

2近似値比アルゴリズムによる解を $J_1\subset\{1,2,\dots,n\}$ とする．
与えられた $\varepsilon$ に対して， $t=\max\left\{1,\frac{\varepsilon v_{\mathrm{max}}}{n}\right\}$ と置く．
各要素について $v_i'=\lfloor\frac{v_i}{t}\rfloor$ と修正したinstanceについて $C=\frac{2\sum_{i\in S_1}v_i}{t}$ 動的計画法を用いて得られる解を $J_2=\{1,2,\dots, n\}$ とする．
$\sum_{i\in J_1}v_i$ と $\sum_{i\in J_2}v_i$ を比べ，大きいほうを出力する．また，その解を $S$ とする．
- 実行時間
  動的計画法による計算時間が支配的．
  $O(nC)=O(\frac{n\sum_{i\in S_1}v_i}{t})=O(n^2\cdot\frac{1}{\varepsilon})$ ．
- 近似値比
  最適解を $S^*$ と書くことにすると，
  $\sum_{i\in S_2}v_i\ge \sum_{i\in S_2}tv_i'=t\sum_{i\in S_2}v_i'\ge t\sum_{i\in S^*}v_i=\sum_{i\in S^*}tv_i'> \sum_{i\in S^*}(v_i-t)\ge\sum_{i\in S^*}v_i -nt$
  $t=1$ のときは， $S_2$ は最適解であり，そうでないときは上の不等式より
  $(1+\varepsilon)\sum_{i\in S}v_i\ge \sum_{i\in S_2}v_i+\varepsilon\sum_{i\in S_1}v_i\ge \sum_{i\in S^*}v_i$
  すなわち， $\sum_{i\in S}v_i\ge\frac{1}{1+\varepsilon}\sum_{i\in S^*}v_i\ge(1-\varepsilon)\sum_{i\in S^*}v_i$ となるので $1-\varepsilon$ 近似値比である．
- 以上よりKNAPSACK問題はFPTAS

$\mathcal{P}=\mathcal{NP}$ でない限り,KNAPSACK問題には，最適解と高々定数差しかない近似解を求める多項式時間アルゴリズムが存在しない．
- $v_i$ すべてに，十分大きい定数を掛けると近似解が最適解となるので $\mathcal{P}=\mathcal{NP}$ となる．

↑

内容 †

計算量理論とは、計算の難しさの学問。
- 例）n都市TSP
  n頂点の重み付き単純グラフ上の閉路で、各頂点をちょうど一度ずつ訪れる。
  辺の重みの和を最小にする閉路を求める問題。
  有限・離散なので解は有限時間内に計算可能。
  しかしそのために必要な計算量は指数オーダー。
  nが大きくなると実用時間内では実行不可能。
  - 素朴な解法
    (n-1)!通りの巡り方での距離を全て計算・比較。
    路一つあたりの計算量が10^(-6)sでも、n=50くらいで計算量は10^50年。
  - cf)ある頂点から他の全ての頂点への最短路を求める問題はO(|V|^2+|E|) Dijkstra's Algorithm
  - TSPはどんなアルゴリズムでも、(最悪の場合)O(n^c)で解くことはできなさそう。NP問題
     ミレニアム懸賞問題,P≠NP問題

NP完全性の理論
- NP:Nondeterministic Polynomial,非決定性多項式時間

n要素全順序集合のソーティング
- Insert Sort O(n^2)
  - n個の整列されたリストにn+1個目の要素を適切な場所に挿入する。
- Bubble Sort O(n^2)
  - リストから順序関係が壊れている部分を探し、正す。
- Heap Sort O(n log n)
  - 要素からヒープツリーを作って、取り出す。
- Quick Sort 平均的にはO(n log n)、最悪ではO(n^2)
  - 中間要素を選び、それより大きい部分リストと小さい部分リストを選び出し、連結する。
- Merge Sort O(n log n)
  - 分割統治。リストを二つに分け、それぞれをソートし、順序の整合が取れるようにマージ。
- どんなアルゴリズムでもΩ(n log n)の時間がかかる。
  (memo:データに制約をつければO(n)にもなりうる。Radix Sort)

Linear Decision Tree
- プログラムの実行パスをツリーの形で全て書き表したもの。
  葉の部分に実行結果が現れる。
  Insent SortのLinear Decision Treeの高さは有限。
  各比較について分岐が一つできる。
  最も木の高さが高くなる最悪のパスでは、O(n^2)になる。
- 正しいソーティングアルゴリズムでは、出力になり得る組み合わせはn!通り。
  木の高さをできるだけ低くして葉の数を増やすことを考えると、
  (深さ)≧ceil(log[2](n!))=O(n log n)
  二要素の比較だけを使ってソートするときの計算量の下限はO(n log s)
  Linear Decision Treeで表したときにバランスの取れた二分木になるようなアルゴリズムが最良のソーティングアルゴリズム。

行列積
- A,B ∈ R^(n×n)
  C = AB
  c[i][j] = Σ[k=1,n]a[i][k]b[k][j]
  式をそのまま計算すると、O(n^3)
  これより計算量の少ない計算方法は存在するだろうか？
- 行列をうまく分割して計算するとO(n^log[2]7)≒O(n^2.807)で計算できる。Strassenのアルゴリズム
- 現在ではO(n^2.386)まで下げられている。下限はΩ(n^2)以上だとしかわかっていない。

漸近的性質
関数f,g:N⇒Nについて
- O
  f(n) = O(g(n))⇔∃n,∃c,∀m≧n. f(m)≦c*g(m)
- Ω
  f(n) = Ω(g(n))⇔∃n,∃c,∀m≧n. f(m)≧c*g(m)
- Θ
  f(n) = Θ(g(n))⇔f(n)=O(g(n))∧f(n)=Ω(g(n))
- o
  f(n)=o(g(n))⇔lim[n→∞]f(n)/g(n)=0

入力サイズnについて、アルゴリズムAの計算時間t(n)がどう増えてゆくか。
- P: t(n)がnの多項式のオーダーとなるアルゴリズムが存在する問題族
  多項式オーダー：O(n^c),
  n,n log(n),n^2,√n,…
- EXP:t(n)がnの指数関数のオーダーとなるアルゴリズムが存在する問題族
  指数関数オーダー(singly exponential):O(2^p(n)),p(n)=O(n^c)
  2^n,n!,n^n=2^(n log(n)),3^(n^2)
- P⊂EXP, nを十分に大きくすると常にEXPの問題の方が大きくなる。
  EXPに属する問題は手におえないくらい計算時間が長くなる。
  P:tractable 手に終える
  Pより上:intractable 手に負えない
  ではEXPとPの境界はどこにあるか。
  それより難しい問題はどう解くか。

計算の難しさ。（上に行くほど難しい。）
- undecidable:計算不能、アルゴリズムが存在しない。
  Turing Machineの停止問題
- decidable:計算可能、アルゴリズムが存在する。
  - 多重指数オーダーで解ける。 Presburger Arithmetic
- intractable:実行不可能、多項式オーダーでは解けない。
  - NP完全問題。非決定性チューリングマシンで多項式オーダーで計算できる。
    境界はまだ曖昧。
    TSP,SAT,coloring
- tractable:実行可能、多項式オーダーで解ける。

アルゴリズムとは何か
- 計算とは、状態遷移だ。
  - Turing Machine
    有限長のプログラム(内部状態)と無限の長さの一次元記憶媒体(テープ)を持った仮想的な機械。
  - TM=(Γ,Σ,Q,δ)
    Γ=Σ∪{b} テープのセルに書く記号の集合。
  - Σ 問題を記述する記号の集合。alphabet
  - Q 機械の内部状態の集合。有限。
    q[0]：初期状態
    q[y]：停止状態、受理
    q[n]：停止状態、非受理
  - δ:Q×Γ→Q×Γ×{+1,-1} 遷移関数。現在の状態と現在地のテープの記号から、
    次の時刻の状態とテープに上書きする値、テープ上の位置の変化を出す関数。
  - 初期状態から、遷移関数に従ってテープ上に記録されたデータを書き換えながら
    内部状態とテープ上の位置を変化させ、停止状態になるまで動き続ける。
    停止状態になったらyes,noのいずれかを返す。
    停止しないこともありうる。
    テープ上に入力を与え、出力としてyes,noを返す計算のモデル。
  - 現在のコンピュータで多項式時間で解ける問題はチューリングマシンでも多項式時間で解ける。逆も成立。
  - δが一価の関数→決定性チューリングマシン
    δが多価関数→非決定性チューリングマシン

決定性チューリングマシン(DTM,Deterministic Turing Machine)
- 通常のチューリングマシン。同じ入力に対して同じ出力を返す。遷移関数が一価関数。
- 計算資源、サイズnの入力に対して最悪の場合の量を指す。
  time complexity：遷移関数を適用する回数。
  space complexity：headが少なくとも一度見たセルの数。
- P：チューリングマシンでの時間計算量が、入力のサイズの多項式で押えられるアルゴリズムが存在する問題。
  PSpace：空間計算量が、入力のサイズの多項式で押えられるアルゴリズムが存在する問題。

PTime ⊂ PSpace ⊂ ExpTime
- 空間計算量がnの多項式で押えられる問題は、時間計算量はexp以下になる。
- 無限ループに陥らないアルゴリズムの実行中には、状態遷移の過程で、同じ状態になることはできない。
  空間計算量が多項式で押えられると、状態遷移で通過できる状態数は指数オーダーで押えられる。

非決定性チューリングマシン(NTM,Nondeterministic Turing Machine)
- 同時に複数の状態をとりうる、遷移関数が多価関数になりうる拡張されたチューリングマシン。並列計算のモデル化？
- 計算資源
  time complexity：NTMを次々に分岐させながらステップを進めて行き、最も早くyesを返して停止した分岐までのステップ数。
  space complexity：最も早くyesを返して停止した分岐での、少なくとも一度見たセルの数。
NP：非決定性チューリングマシンでの時間計算量が、入力サイズの多項式で押えられるアルゴリズムが存在する問題。

PTime ⊂ NP ⊂ PSpace
- NTMをDTMでシミュレート。各ステップを幅優先探索。
  バックトラックの状態復元に使うメモリは、深さが多項式オーダーなら、多項式オーダー。

並列計算をしたときや、計算機が速くなったときの、同一時間で解ける問題のサイズ。
- プロセッサ数がp倍になったときに、
  O(n) p倍
  O(n^2) √p倍
  O(2^n) log p倍。

多項式時間変換(Polynomial-time Reducibility)
- ハミルトン閉路(HC,Hamilton Circuit)問題
  入力:グラフ
  出力：入力グラフがHCを持つか否か。
- 巡回セールスマン問題の判定
  完全グラフ。距離関数。パラメタ一つ。
  総長がパラメタの値以下のHCが存在するかどうか。
- ある問題クラスΠの、任意のインスタンスが、別のあるクラスΠ'のインスタンスに多項式時間で帰着できるなら、
  ΠはΠ`に多項式時間変換可能だという。
  f:Π→Π'. π:yes⇔f(π):yes
- ハミルトン閉路問題は、多項式時間で巡回セールスマン問題に多項式時間で変換可能。
  完全グラフ化して、追加したグラフの重みを大きくしておく。

NTM(Oracle版)
- Guessing Module付きのDTM
- 入力xがセル1からセル|x|まで与えられている。
  「Advice」をGuessing Moduleがセル(-1)から左に書く。
  Guessing Moduleを停止してDTMとして起動。処理。停止。
- NTMでどの分岐をすべきかをあらかじめ外部から与えたもの。
- NTMを使うと多項式時間で解ける問題は、DTMで多項式時間で正解を検証できる問題。

命題論理の充足可能性判定問題(SAT,Satisfiability)
- 入力：CNF命題論理式(CNF,Conjunctive Normal Form,∧標準形)
- 出力：入力の論理式を満たす真偽値の組み合わせがあればTrue,なければFalse
- 入力は論理変数をn個持った論理式で、論理変数と￢と∨からなる節(Clause)を∧で連ねた形に標準化されたもの。
  うまく論理変数の値を選んだとき、論理式全体を真にできるとき、その論理式は充足可能。
  どの組み合わせを選んでも真にできないとき、恒偽、充足不可能と呼ぶ。
- この充足可能性問題は

ここLostかも。後で補完。

NPの中で多項式時間還元を考えることでNPを分類する。
多項式時間還元で擬順序を導き、擬順序から導かれる同値関係でNPを分割。
分割された塊の間には、多項式時間還元によって半順序が入っている。
この半順序には最小元と最大元が存在する。最小限はP、最大限はNP完全問題。
NP完全
NP問題クラス $\Pi$ のうちで、任意のNP問題クラス $\Pi'$ の問題を
多項式時間で $\Pi$ に帰着できるなら、
$\Pi$ はNP完全という。
NP完全な問題のどれか一つに多項式時間アルゴリズムが存在すれば、
任意のNP問題が多項式時間で解ける。 $P=NP$
NP完全な問題には多項式時間アルゴリズムは存在せず、
$P\neq NP$ だろうという考えが大勢になっている。
SAT,TSPなど、多くの問題がNP完全であることがわかっている。

Karpのreduction
- 問題クラス&mimetx(\Pi);がNP完全であることを示したいときには、
  $\Pi$ がNP問題であることと、適当なNP完全問題 $\Pi'$ を
  $\Pi$ に多項式時間還元ができることを示せばいい。
  ではどのNP完全問題に帰着できることを示すのがよいか。
- SATはNP完全。SATを他の問題に連鎖的に帰着させてNP完全性を示す。
  $\mathrm{SAT} \prec \mathrm{3SAT}$
  $\mathrm{3SAT} \prec \mathrm{3DM}$
  $\mathrm{3DM} \prec \mathrm{PARTITION}$
  $\mathrm{3SAT} \prec \mathrm{VC}$
  $\mathrm{VC} \prec \mathrm{HC}$
  $\mathrm{HC} \prec \mathrm{TSP}$
  $\mathrm{VC} \prec \mathrm{CLIQUE}$
- 3SAT
  入力：3-CNF論理式(各節が3つの命題からなる和積標準形の論理式)
  和積標準形論理式の節は、論理積で連なっている論理和からなる塊。
  出力：論理式を真にする命題の組み合わせが存在するか。
  - 3SATはNP問題。SATはNP問題。3SATはSANの部分クラス。
  - 任意のSATの問題を3SATに多項式時間還元できることを示せば、3SATがNP完全であることを証明できる。
    任意のSATの問題の各節について、
    節に含まれる論理変数の数が1,2,3のときには、新たに論理変数を追加して水増し。3変数にする。
    $x \equiv (x\vee y) \wedge (x \vee \bar{y})$
    論理変数の数が4以上。例えば5のときには、
    $a\vee b \vee c \vee d \vee e \equiv (a\vee b \vee x)\wedge(\bar{x}\vee c \vee y)\wedge(\bar{y}\vee d \vee e)$ と変形すれば3変数にできる。
    ゆえに任意のSATの問題は多項式時間で3SAT問題に帰着可能。
  - cf)2SAT
    入力を2-CNF論理式に限った2SATは $O(n)$ 、P問題。
- VC(Vertex Cover)。無向グラフの被覆問題。
  入力：無向グラフとパラメタK。
  出力：サイズK以下のVertex Coverが存在するか否か。
  - 3SAT問題をVCに帰着すれば、VCがNP完全であることを示せる。
    VCはNP問題。解が与えられればそれがサイズK以下の被覆になっていることは
    多項式時間で確かめられる。
    3SATの論理式をグラフに変換し、充足可能性とVCの存在が同値になるようにKを選ぶ。
    各論理変数とその否定を頂点とし、肯定形と否定形を頂点でつないで２点からなるグラフを作り、
    各節に対応して、その論理変数に応じた三角形のグラフを作り、
    節に対応するグラフの頂点と、それに対応する論理変数を繋ぐ。
    Kとして、(論理変数の数)+2*(節の数)をとってVC問題とすると、 3SATをVCに帰着できる。
  - Vertex Cover
    任意の辺の少なくとも一方が含まれるように、グラフの頂点からいくつかを選び出す。
  - cf)２部グラフについては、最小VC探索はP問題。最小VCは最大マッチングを与える。

先生会議中。代理の人が講義。
PSPACE = NPSPACE
- PSPACE
  決定性チューリングマシンで、入力サイズに対して領域計算量が多項式オーダーで計算可能。
- NPSPACE
  非決定性チューリングマシンで、入力サイズに対して領域計算量が多項式オーダーで計算可能。
- 有向グラフの連結性判定
  入力：有向グラフ。 $|V|=n$
  出力：頂点s,tを結ぶ長さが $2^k$ 以下の路があるか否か。
  - STCONのアルゴリズム
    長さが $2^k$ 以下の有向路があるか否かを返す関数reachを使って、
    $\mathrm{reach}(s,t,\log n)$ を実行すればよい。
    $\mathrm{reach}(v_1,v_2,k)\{$
    $\mathrm{if}(k=0)\{\mathrm{return}\ v_1 == v_2 \vee (v_1,v_2)\in E \}$
    $\mathrm{else} \{$
    $\mathrm{foreach}(v'\ \in V)\mathrm{return}\ \mathrm{reach}(v_1,v',k-1) \wedge \mathrm{reach}(v',v_2,k-1)$
    $\}$
  - 一回の再帰には $O(log n)$ の計算領域、再帰の深さは $O(log n)$ なので、
    計算領域は $O((log n)^2)$ だけ必要、PSPACE。
- PSPACE = NPSPACEの証明
  PSPACE $\subset$ NPSPACE は定義から自明。
  NPSPACE $\subset$ PSPACE を証明するために、
  チューリングマシンのスナップショットからなるグラフを考える、
  各スナップショットをノードにし、遷移規則から枝を定める。
  計算領域がNTMで $p(n)$ であるとすると、頂点数は、(状態数)*(使う領域幅)*(テープの内容)^(使う領域幅)で、 $O(e^{p(n)})$
  このグラフに対してTMでSTCONのアルゴリズムを走らせると、
  領域計算量は $O(p(n)^2)$ なので、TMで多項式空間計算量でシミュレート可能。
- STCONはNLOG完全。NTMでO(log(n))で計算可能。
- LOG $\subset$ NLOG $\subset$ (LOG)^2
- STCONが $\log n$ SPACEで計算可能かどうかは未解決。
- Randomized Algorithmなら $\log n$ SPACEで計算可能。
- 無向グラフなら $\log n$ SPACEで計算可能。

NP-Completeの意義
- P $\subset$ NP $\subset$ PSPACE=NPSPACE $\subset$ EXPTIME $\subset$ NEXPTIME
- NP完全問題が一つでもPであることがわかれば、P=NP。
  任意のNP問題がPであることがわかる。
- P問題はTractable、それ以外はIntractableだと考え。
  P=NPではないことを想定して、NP完全であることを示すことで、問題がIntractableであることを示す。
  NP完全であることを示すことがパラダイムになっている。

Ristriction
- NP完全な部分問題を含むNP問題は、NP完全問題。
  問題を限定した上でNP完全性を示し、全体の問題クラスもNP完全であることを得る。

部分グラフ同型判定問題
入力：無向グラフ２つ。 $G_1,G_2$
出力： $G_1$ が $G_2$ と同型な部分グラフを持つか否か。

CLIQUE
入力：無向グラフ。 $G$
出力： $G$ がサイズk以上の完全グラフを部分グラフを持つか。
- 同型になる部分グラフと同型写像が与えられれば、確かめることは多項式時間で可能。NP問題。
- CLIQUEは部分グラフ同型判定問題の部分問題。
  CLIQUEがNP完全ならば部分グラフ同型判定問題はNP完全。

Local Transformation
Component Design

NP完全性を示す事で、問題が難しいことを示す。
問題の簡単さを示すには、多項式時間で解けるアルゴリズムを見つければよい。
- SATはNP完全問題。
  3-SATもNP完全問題。
  2-SATはP問題で、O(n)で解ける。
  SATは節の中の論理変数の数で階層化できる。
  k-SATは、k=2ではP問題。k≧3ではNP完全問題。
  同様な階層化はk部グラフのマッチング問題でもできる。
  - HORN
    SATの部分問題。各節に正リテラルが高々１つ。P問題。O(n)で解ける。

難しさの異なる似た問題をNP完全か、Pかで類別する。
- 枝長非負なグラフの最短路問題はP問題。(Dijkstra法)
- 最長単純路問題はNP問題。
  単純路：同じ頂点を２度は通らない路。
  - 有向閉路のないグラフでの最長路問題はP問題。(DFS,topological sort)

グラフの最小点被覆
点による枝の被覆。NP完全問題。
グラフからいくつか点を選び出し、各枝について
その枝の端点のどちらかは選ばれるようにする。
選ばれる点数はできるだけ少なくする。
２部グラフの点被覆を求めるのはP問題。
- 最大マッチング・最小点被覆定理
グラフの最小枝被覆
枝による点の被覆。P問題。
グラフから枝をいくつか選び出し、全ての点について
その点につながる枝のどれかは選ばれているようにする。
選ばれる枝数はできるだけ少なくする。

最小切断
点集合を２つに分け、その間をまたぐ枝数をできるだけ少なくする。
P問題。
最大切断
点集合を２つに分け、その間をまたぐ枝数をできるだけ多くする。
NP完全問題。
平面グラフの限定すればP問題。
- 最大流・最小切断定理。

グラフの次数に着目。
点 $v\in V$ について、 $d(v)$ は、 $v$ に接続する枝の数。
グラフの次数は、各点の次数の最大値。
Vertex Cover、Hamilton circuitなどは、次数2以下のグラフについてはP問題。それを超えるとNP完全。

数系のNP完全問題
- PARTITION
  入力：n個の整数。
  出力：入力を2分割して、それぞれの和を等しくできるか否か。
  - 困難さ
    分割の仕方は $2^{n-1}$ 。
    整数の大きさに制限がない。

11/27は休講

動的計画法(DP,Dynamic Programming)
- 全体での最適な構造が、部分的にも最適な構造になっている。
- Shortest Path
  階層化された有向グラフ上での最短経路を求める。
  $p(v)$ を始点から $v$ への最短路長とすると、
  $p(v)=\mathrm{min}\{p(u)+d(e)|e=(u,v)\in E\}$
  始点からある層の各点への最短路の値から、次の層の各点への始点からの最短路を求められる。

PARTITION
入力：n個の正整数出力：その和が等しくなるように入力された整数を
二つのグループに分割することができるか否か。
- DPで解く
  $t_{ik}$ を、 $a_{1},a_{2},\cdots,a_{i}$ の部分集合で、
  和が $k$ のものが存在すればTrue,存在しなければFalse。と定義すれば、
  $t_{n,k'},k'=\sum_{i=1}^{n}\frac{a_{i}}{2}$ が解。
  $t_{ik}$ は $t_{ik} = t_{i-1,k} \vee t_{i-1,k-a_{i}}$ を満たすので
  $i$ について次々に計算できる。
  時間計算量は $t$ のテーブルの大きさ分、 $O(n\sum_{i=1}^{n}a_{i})$ で解ける。
  $\sum_{i}a_{i}$ の大きさがnの多項式で押さえられるならば、多項式時間で解ける。
  入力長は $\sum_{i=1}^{n}\mathrm{ceil}(\log_2 a_{i})$ ほど、
  $\sum_{i=1}^{n}a_{i}$ は入力長に対して指数オーダー。
- Number Problem
  数がからむ問題では、入力長に対し、数がとても大きくなりうることが難しさのポイント。
  問題の構成要素の個数と独立な値になっている。
  問題のインスタンス $I$ の入力長を $\mathrm{Length}[I]$
  現れる数の最大値を $\mathrm{Max}[I]$ とすると、
  PARTITIONは $\mathrm{Length}[I]$ に対して多項式時間。
  これを擬多項式時間アルゴリズム(pseudo-polynomial)と呼ぶ。
  P問題は $\mathrm{Length}[I]$ について多項式時間でなければならない。
  PARTITIONは擬多項式時間アルゴリズムは存在するが、NP完全なので
  真の多項式時間アルゴリズムはおそらく存在しない。
  - 任意のNP完全な問題に擬多項式時間アルゴリズムは存在するか？
    NP完全問題をさらに分割できる。

Strong NP-Complete
NP完全問題で、 $\mathrm{Max}[I]=O(\mathrm{poly}(\mathrm{Length}[I]))$ の場合でもNP完全のとき、
その問題は強NP完全問題と呼ぶ。
(P≠NPの仮定のもと、)強NP完全は擬多項式時間アルゴリズムを持たない。
- TSPは強NP完全、非整数問題は強NP完全。

計算問題
ここまで扱ってきたのは受理問題。戻り値はyes,no。
計算問題や探索問題について難しさの尺度を与えられないか。
Turing還元のもとで問題クラスを分類する。//と、NP困難(NP-hard)が現れる。

Search Problem
探索問題 $\Pi$ とは、
インスタンスの集合 $D_{\Pi}$ で、
各インスタンス $I\in D_{\Pi}$ に対して
解 $S_{\Pi}[I]$ が存在。
$\Pi$ を解くアルゴリズムとは、
$S_{\Pi}[I]=\phi$ のとき、"no"と答え、
そうでないとき、 $S_{\Pi}[I]$ の要素を1つ出力するアルゴリズム。

Poly-time Turing Reduction
$\Pi \leq \Pi'$
$\Pi'$ を単位時間で解くサブルーチンを使っていいときに、
$\Pi$ を多項式時間で解くアルゴリズムが存在すること。
$\Pi'$ が多項式時間で解けるならば、 $\Pi$ も多項式時間で解ける。

NP困難(NP-hard)
NP完全な問題にTuring Reductionできる問題クラスをNP困難な問題と呼ぶ。
NPなNP困難問題はNP完全問題。
TSP判定版はNP完全。TSP探索版はNP困難。

Coping with NP-Complete Problems
NP完全問題は難しい $\Rightarrow$ 近似的に解く。
Poly-timeでできるだけいい近似解を探す。
Poly-timeで高い確率で厳密解を探す。

bin-packing
一次元の引越しトラック最小化問題、NP困難。
n個の品物 $u_{1},u_{2},\cdots,u_{n}$
品物のサイズ $s(u)$ 、 $0\geq s(u) \geq$
容量1のビンいくつかに品物を詰めて行き、ビンの数を最小化する。
$\mathrm{OPT}(I)$ を最適解
$A(I)$ をアルゴリズム $A$ による解。
$\forall I\in \Pi. A(I) \leq a\mathrm{OPT}(I) + b$ となるアルゴリズム $A$ を
この問題の近似アルゴリズムと呼ぶ。 $a$ は近似値比と呼ぶ。
- 単純な方法
  FF(First Fit)
  ビンを十分多く準備しておき、各品物について
  ビンを左から見ていき、最初に詰められるビンに詰めて行く。
  $\mathrm{FF}(I)\leq 2\mathrm{OPT}(I)$ の近似アルゴリズム
  - この証明のためには、 $\mathrm{OPT}(I)$ の値を何らかの形で評価する必要がある。
    「液体版」bin-packingの解で下から抑えられる。
    ~~オレンジジュースとコーヒーと味噌汁とコーンポタージュを~~
    $\mathrm{ceiling}(\sum_{i=1}^{n}s(u_{i}))\leq \mathrm{OPT}(I)$
    FFでは半分以下しか入っていないビンは高々1つ。
    $\mathrm{FF}(I)\leq \ceiling(2\sum_{i=1}^{n}s(u_{i}))$
  - 実際は、 $\forall I. \mathrm{FF}\leq \frac{17}{10}\mathrm{OPT}(I)+2$
    $\exists I. \mathrm{FF}\geq \frac{17}{10}\mathrm{OPT}(I)-1$ が成立。
    近似値比は $\frac{17}{10}=1.7$
- FFD(First Fit Decreasing)
  まず品物を降順にソートしてからFFで詰める。
  FFDだと、 $\forall I. \mathrm{FFD}(I)\leq \frac{11}{9}\mathrm{OPT}(I)+4$
  $\exists I. \mathrm{FFD}(I)=\frac{11}{9}\mathrm{OPT}(I)$ が成立。
  近似値比は $\frac{11}{9}=1.222$
  worst-caseでFFよりもFFDの方が優れていると、定量的に言えた。

任意の正数 $\varepsilon$ について、近似値比 $1+\varepsilon$ が達成できる場合と、
$P\neq NP$ の仮定のもと、 $\exists c > 1$ 、近似値比 $\geq c$ となる場合がある。
bin-packingは前者。TSPは後者。

近似アルゴリズム
- Metric TSP
  完全グラフと距離関数の形で問題が与えられたTSP。
  距離関数は三角不等式を満たす。２点間の最短距離は直に２点をつないだもの。
  NP困難。近似値比2の近似アルゴリズムが存在する。
- Euclidean TSP
  ２次元平面上にn点が与えられ、距離がユークリッド距離のMetric TSP。
  まだNP困難。

MST(Minimum Spanning Tree)近似
- グラフの最小木 $T$ を求め、その各枝を２重化したものを $T'$ とする。
  $T'$ のEuler閉路を求め、閉路を順に巡る。２回目以降では点をスキップ。
  Metric TSPの最適解はハミルトン閉路、枝を一つ除けば木になっている。
  最小木は部分木の中でもっとも短いものなので、( $T$ の長さ) $\leq \mathrm{OPT}(I)$
  枝を２重化すると、( $T'$ の長さ) $=2$ (\mimetex(T);の長さ)
  MST近似ではいくつか点をスキップし、Metric TSPでは点をスキップすると全長は短くなるので、
  $\mathrm{MST}(I)\leq$ ( $T'$ の長さ) $\leq 2\mathrm{OPT}(I)$
  $\mathrm{MST}(I)\leq 2\mathrm{OPT}(I)$ 、近似値比２のアルゴリズム。
  - Euler閉路：各枝を一度ずつ通る閉路。各頂点の次数が偶数なら存在する。
MM(Min-weight Matching)近似
- グラフの最小木 $T$ を求め、奇数次数点間の最小重み完全マッチング $M$ を求める。
  $T\cup M$ のEuler閉路を求める。後はMSTと同じ。
  ( $T$ の長さ) $\leq \mathrm{OPT}(I)$
  ( $M$ の長さ) $\leq 0.5\mathrm{OPT}(I)$
  $\mathrm{MM}(I)\leq = 1.5\mathrm{OPT}(I)$
  - 最小重み完全マッチング
    辺の集合から、すべての点を覆うようにいくつかを選び、
    枝の重みの和を最小化する。

NN(Nearest Neighbor)
未到達の点の中で、最も近い点を訪問する。
全点に到達していたら、始点に戻って終了。
Metric TSPでは、
$\forall I.\mathrm{NN}(I)\leq \frac{1}{2}(\mathrm{ceil}(\log_{2}n)+1)\mathrm{OPT}(I)$ $\exists I.\mathrm{NN}(I)\leq \frac{1}{3}(\mathrm{ceil}(\log_{2}n)+\frac{4}{3})\mathrm{OPT}(I)$

plannar Euclidean TSP
PTASが存在する。
- PTAS
  $\forall \varepsilon > 0$ に対して、
  近似値比 $1+\varepsilon$ の多項式時間近似アルゴリズム。
Metric TSP 近似値比1.5の多項式時間近似アルゴリズムが存在する。
$P\not{=}NP$ の仮定のもと、PTASは存在しない。
一般のTSP
$P\not{=}NP$ の仮定のもと、
定数近似値比の多項式時間近似アルゴリズムは存在しない。

理学部の講義は1/10かららしいので、今日はおまけ講義

最長片道切符
Hamilton Pathがないネットワークで、
できるだけ総長の長い単純パスを求める。
Hamilton Pathのないネットワークで、
各点を少なくとも一度訪れるパスで、最短のものを求める。
- 入力：有向グラフ $G=(V,E)$
  各枝の枝長 $d(e)$ 、負の有向閉路はない。
- 出力：各点を少なくとも一度訪れる最短パス。
  - 通常のTSPに帰着する。
    有向完全グラフ $K_{|V|}$ を用意し、
    枝長を $G$ 上での最短経路長に設定する。
    各点を少なくとも一度訪れる最短ルートは、
    有向完全グラフ $K_{|V|}$ 上で各点をちょうど一度ずつ訪れる最短パスになっている。

試験問題にしようと思っていた問題。
有向グラフ上での今の問題を解きたい。
この問題がNP-hardであることを示せ。TSPがNP-hardであることは仮定してよい。
多項式時間近似アルゴリズムで、近似値比1.5のものを与えよ。
- 「有向」だととても困難。無向にしてMetric TSPにすればできる。

Chinese Postman
全路線を最短の長さで巡りたい。
無向グラフ上のすべての枝を少なくとも一度通る閉路のうち、総長が最短のものを求めよ。
これはP問題。 $O(n^3)$ のアルゴリズムが存在する。
- 奇数次の点のみからなる完全グラフで、各枝の枝長が元のグラフの最短路長となるものを用意する。
  その完全グラフ上で、総長最小の完全マッチングを求める。
  マッチングで得られた枝を元のグラフに付け加えて、元のグラフをオイラーグラフにする。
  このオイラーグラフ上でオイラーグラフを求めれば、それが最適解。

TSPの近似可能性
- MetricTSPには近似値比1.5の近似アルゴリズムが存在する。
- $P\neq NP$ の仮定のもと、一般のTSPには、
  定数近似値比の多項式時間近似アルゴリズムは存在しない。
  もし存在するなら、それを使ってHCを多項式時間で解けてしまう。
  HCがあるかどうかを判定すべきグラフに、枝を追加し、完全グラフにする。
  元からあった枝には重み１を、追加した枝には充分大きな重みを割り当てる。
  このグラフについてTSPの近似アルゴリズムを使って、
  枝長nのHCがあると判定されたらもとのグラフにもHCが存在し、
  充分大きな値のHCが最短HCならもとのグラフにHCは存在しない。
- Euclidian TSP
  任意の $\varepsilon > 0$ に対して、近似値比 $1+\varepsilon$ のアルゴリズムが存在する。
  PTAS(Polynomial Time Approximation Scheme) FPTAS(Fully PTAS)、PTASで、timeが入力長と $\frac{1}{\varepsilon}$ の多項式とした場合。

Knapsack問題
n個の品物について、サイズ $s_i$ 、利得度 $v_i$ が与えられている。
サイズの和が容量B以下で、利得度を最大にする組み合わせを探索する。
$\mathrm{OPT} = \mathrm{max} \sum_{i=1}^{n}v_{i}x_{i}$
s.t $\sum_{i=1}^{n}s_{i}x_{i} \leq B$ 、 $x_i = 0,1$

緩和問題
- $\mathrm{OPT}_\mathrm{Relax} = \mathrm{max} \sum_{i=1}^{n}v_{i}x_{i}$
  s.t $\sum_{i=1}^{n}s_{i}x_{i} \leq B$ 、 $0 \geq x_i \leq 1$
  緩和問題の解は $\mathrm{OPT} \geq \mathrm{OPT}_\mathrm{Relax}$
  緩和問題で最適値が0,1なら、もとの問題の最適解。
  うまくしらみつぶしに調べる。Branch-and-Bound
- 緩和問題はGreedyに解ける。

PTAS
Partial Enumeration
- パラメタkについて、個数k以下の部分集合を列挙。
  各部分集合について、Greedyに最適なものを探す。
  - 最適な入れかたについて、
    最適な品物数がk個以下の時には、最適解が見つかる。
    k+1の時には、利得度が大きい順にk個まで

Knapsack問題、Partial Enumeration
1または2の場合を試験問題として出すかも。

FPTAS
Knapsackの単純なPTASは近似値比は $1+\varepsilon$ で、計算時間は&mimetex(O(n^{1+\frac{1}{\varepsilon}}\ ));
FPTAS、近似値比 $1+\varepsilon$ で、計算時間を入力長と $\frac{1}{\varepsilon}$ の多項式にする\\ 。
- Scaling + Pseudo-Poly-Time
  Knapsack問題のPseudo-Poly-Timeアルゴリズムで、 $O(n^{2}V \mathrm{log}(nVS))$
  V:品物の利得度の最大値。S:品物のサイズの最大値。
  利得度について動的計画法
  利得度を小さく変換すれば真の多項式時間で計算できる。
- 原問題
  品物 $u_{i}$
  利得度 $v(u_{i})$
  サイズ $s(u_{i})$
- スケール変えて粗視化する。 $v'(u_{i})=\mathrm{ceil}(\frac{v(u_{i})}{K})$
  $K=\frac{1}{\epsilon}$ ととれば、擬多項式時間アルゴリズムが近似値比 $1+\varepsilon$ で、計算時間 $O(n^{3}\frac{1}{\varepsilon}\mathrm{log}(nVS))$ の多項式時間近似アルゴリズムになる。

決定問題、最適化問題、計算問題、列挙問題

列挙問題
与えられた問題の解を全て重複無く見つけ出す問題、パスの列挙、クリークの列挙など。
問題の構造を把握する上で有効な手法。
解の数が膨大になることがある。すべての解の列挙ではなく、列挙する対象を選ぶことが大事。
全てのクリークではなく、極大なクリークの列挙をする。
全てのパスではなく、最短パスを列挙する。
- グラフのクリーク列挙。
  完全部分グラフを列挙する。
  最大クリークを求める問題はNP-Complete
  極大クリークを求める問題は多項式時間でできる。 $O(|V||E|)$
  - クリークの単調性
    クリークの点部分集合から誘導されるグラフはクリーク。
    １点集合から始めて、集合に点を順番に追加していき、クリークにならなくなるまで点を追加する。
    クリークでなくなる直前が極大クリーク。
    頂点に番号をつけておくと、クリークに辞書式順序が入る。
    極大クリーク $K$ から、番号が大きい順に一つずつ点を除いていった部分クリーク $K'$ について、 $K'$ を含むクリークで、辞書式順序最小のものが $K$ でないときに、それを $K$ の親と呼ぶ\\ 。
    この親子関係で木を作り、深さ優先探索をすれば、クリークを重複無く全て列挙することができる。
    非巡回的な親子関係と、子供を見つける多項式時間アルゴリズムがあれば、多項式時間列挙ができる。
  - 子供候補の見つけかた
    クリーク $K$ に隣接する頂点 $i$ と頂点 $i$ に隣接する頂点からなるクリークを含む
    辞書式さ衣装のクリークを $K[i]$ とする。
    $K'$ が $K$ の子供ならば、 $K[i]=K'$ がいずれかのiについて成り立つ。
    子供ノードの候補 $K'$ と $K$ の親子チェックをして、子ノードを確定する。
    $O(\Delta^2)$ 最大次数の２乗の時間で親を計算できる。探索対象は多くとも $(\Delta+1)^2$ 、
    列挙一つあたりで最大次数の4乗のオーダーで求められる。
    列挙については、列挙にかかった総時間ではなく、一つあたりにかかった時間が多項式時間かどうかが問題となる。
    列挙対象が指数オーダーになることもあるので総時間での多項式性はあきらめる。（多項式時間遅延）

近似は難しさに対抗する手段。
近似の性能の評価は近似値比だけ？

グラフの枝彩色
グラフの枝を塗り分ける。同じ点に接続する枝は違う色にする。
点彩色と同様にNP完全。
2部グラフの枝彩色なら多項式時間アルゴリズムが存在する。
n次完全２部グラフの彩色はn色でできる。
全点の次数がkの２部グラフの彩色はk色でできる。
- 最大次数kの２部グラフの枝グラフは、k色で彩色可能。多項式時間で彩色できる。
- 最大次数kの一般のグラフは、k色で彩色可能か、もしくは(k+1)色で彩色可能。
  この判定はNP-Complete。(k+1)色で塗るのは多項式時間で可能。
  解の比ではなく、解の差に越えがたい壁がある。

$P\neq NP$ の仮定のもと、多項式時間で定数差近似ができない問題が存在する。
グラフの最大安定集合、クリーク、枝彩色問題
基本的な証明技法は背理法。定数差近似kが存在したら、グラフを(k+1)個にコピーした問題を解けば、
$\frac{k}{k+1} < 1$ 、差の絶対値が1未満の2整数は等しい。

計算量理論 のバックアップ(No.16)

計算量理論(Computational Complexity) †

過去問 †

予想問題 †

内容 †

計算量理論のバックアップ(No.16)