1
大学数学基礎解説
文献あり

PCP定理とその証明 (準備編)

314
0
$$\newcommand{argmax}[0]{\mathrm{argmax}} \newcommand{argmin}[0]{\mathrm{argmin}} \newcommand{binset}[0]{\{0,1\}} \newcommand{E}[0]{\mathbb{E}} \newcommand{indicator}[0]{\mathbf{1}} \newcommand{Nat}[0]{\mathbb{N}} \newcommand{poly}[0]{\mathrm{poly}} \newcommand{Real}[0]{\mathbb{R}} \newcommand{UNSAT}[0]{\mathrm{UNSAT}} $$

この記事は計算量理論における偉大な定理の一つであるPCP定理の紹介とDinurDin07による証明を解説する一連の記事のうちの二つ目です. 前回 の続きで, PCP定理の証明をするための準備をします. 具体的には以下の定理を証明するのが全体の目標です.

PCP定理の別の形

ある定数$c>0,k\in\mathbb{N}$, 多項式$p\colon\Nat\to\Nat$, 有限集合$\Sigma_0$と, 与えられた2-CSPのインスタンス$\mathcal{C}$を以下の性質を満たす別のk-CSPのインスタンス$\mathcal{C}'$に変換する多公式時間アルゴリズムが存在する: 任意の2-CSPインスタンス$\mathcal{C}$に対し,

  • $\mathrm{UNSAT}(\mathcal{C})=0 \Rightarrow \mathrm{UNSAT}(\mathcal{C}')=0$
  • $\mathrm{UNSAT}(\mathcal{C})>0 \Rightarrow \mathrm{UNSAT}(\mathcal{C}')\geq c$
  • $\mathcal{C}$の変数の個数を$n$とすると, $\mathcal{C}'$の変数の個数は高々$p(n)$.
  • $\mathcal{C}'$のアルファベットは$\Sigma_0$.

CSPや$\mathrm{UNSAT}$について 前回の記事 にも述べてありますが, 本記事でも改めて以下の章で定義します.

1. 準備

まず, 簡単に記号を述べておきます.

  • 自然数$n\in\mathbb{N}$に対し$[n]=\{1,\dots,n\}$とする.
  • グラフの頂点集合は$V$と書き, 辺集合は$E$で表す. 頂点には番号(順序)があり, $V=\{v_1,\dots,v_n\}$と表せるとする.
  • $\{u,v\}$$uv$と略記する. 基本的に無向グラフを考えるので$uv=vu$である. なお, 多重辺や自己ループも考えうる. 特に断りのない限り, 辺$uv$または$\{u,v\}$と書いたとき, $V$上の順序の意味で$u$$v$より前にあるとする (例えば$\{v_1,v_3\},\{v_2,v_5\}$など).
  • 有限集合$S$に対し, $x\sim S$によって, $x$$S$上一様ランダムに選ばれることを表す. 例えば$\Pr_{x\sim S}[\cdot],\E_{x\sim S}[\cdot]$と書くと$x\sim S$における確率や期待値を表す.

1.1. グラフの基礎用語とエクスパンダー性

グラフの次数, $d$-正則, エクスパンダーという用語に関しては こちらの記事 を参照してください. なお, 自己ループの辺の次数は2としてカウントします. ここでは正則グラフのエクスパンダー性を使うので, 以下の定義と性質だけ知っていれば大丈夫です:

正則グラフのエクスパンダー性

$d$-正則グラフ$G=(V,E)$の隣接行列$A$に対し, $P=\frac{1}{d}A$を遷移確率行列と呼ぶ. $1=\lambda_1\geq \dots \geq \lambda_n\geq -1$$P$の固有値とする (必ず実固有値を持つことが示せる). グラフ$G$$\max\{\lambda_2,|\lambda_n|\}\leq \lambda$を満たすとき, $\lambda$-エクスパンダーであるという.

任意の$n\in\Nat$に対して$n$頂点エクスパンダーグラフは$\poly(n)$時間で決定的に構成できることが知られています.

エクスパンダーグラフの存在性

ある定数$d_0\in\Nat,\lambda_0<1$と多項式時間アルゴリズム$\mathcal{A}$が存在して次が成り立つ:
$n\in\Nat$に対して$\mathcal{A}$$\poly(n)$時間で$n$頂点$d_0$-正則$\lambda_0$-エクスパンダーグラフを出力する.

例えば$n$頂点$d$-正則グラフを一様ランダムに生成すると, Friedmanの定理Fri91により確率$1-o_{n\to\infty}(1)$$2/\sqrt{d}$-エクスパンダーになります (漸近的にラマヌジャングラフになります) 決定的に構成する場合はReingold, Vadhan, WigdersonRVW02の方法などをうまく使うと構成できます. 気になる方は元論文Din07のLemma 2.2などを参照してください.

エクスパンダーグラフの性質として, 以下のエクスパンダー混交補題と呼ばれる有名な結果を使います.

エクスパンダー混交補題

$G=(V,E)$$n$頂点$d$-正則$\lambda$-エクスパンダーとすると, 任意の$S,T\subseteq V$に対して
\begin{align*} \left|E(S,T)-\frac{d}{n}|S||T|\right| \leq \frac{\lambda d}{n}\sqrt{|S||T||\overline{S}||\overline{T}|}. \end{align*}
ここで, $E(S,T)$$S,T$それぞれに端点を持つ辺の集合, $\overline{S},\overline{T}$はそれぞれ$S,T$の補集合を表す.

特に, $|S|\leq \frac{n}{2}$を満たす任意の$S\subseteq V$に対して
\begin{align*} |E(S,\overline{S})| \geq \frac{1-\lambda}{2}d \cdot |S|. \end{align*}

エクスパンダー混交補題の直感などは
エクスパンダーグラフの紹介記事 を参照してください. 紹介記事で丁寧に示したエクスパンダー混交補題では右辺が$\lambda d\sqrt{|S||T|}$でしたが, 同様の証明によって上記の補題のように少し改善できます. 念のためその証明を簡潔に記載しておきます.

後半の「特に, ...」の部分は前半の主張に$T=\overline{S}$を代入して$|\overline{S}|\geq \frac{n}{2}$を用いれば簡単に示せるので, 以後, 前半の主張を証明します.

$G$の隣接行列を$A\in\binset^{V\times V}$, $S,T\subseteq V$の支持ベクトルをそれぞれ$\indicator_S,\indicator_T\in\binset^V$とします. $G$は正則グラフなので, 唯一の第一固有ベクトルは$\indicator=\indicator_V$であり, それ以降の固有ベクトルは全て$\indicator$に直交します. ここで, 二つのベクトル$x:=\indicator_S-\frac{|S|}{n}\indicator, y:=\indicator_T-\frac{|T|}{n}\indicator$はどちらも$\indicator$に直交するので,
\begin{align*} |E(S,T)| &= \indicator_S^\top A \indicator_T \\ &= \left(\indicator_S - \frac{|S|}{n}\indicator\right)^\top A \left( \indicator_T - \frac{|T|}{n}\indicator\right) + \frac{|S||T|}{n^2}\indicator^\top A \indicator \\ &= x^\top A y + \frac{d}{n}|S||T|. \end{align*}
従って
\begin{align*} \left||E(S,T)| - \frac{d}{n}|S||T|\right| &= |x^\top A y| \\ &\leq d\lambda \|x\|\|y\| \\ &= \frac{d\lambda}{n}\sqrt{|S||T||\overline{S}||\overline{T}|} \end{align*}
より主張を得ます.

1.2. 2-CSPの再定義と制約グラフ

3彩色問題のNP完全性より, PCP定理を示す際は2-CSPのみを考えれば良いことになります. 一般にk-CSPとは高々$k$個の変数に依存する制約の集合として定義されましたが, ここでは2-CSPのインスタンスを 頂点を変数として各辺がそれぞれ一つの制約に対応するグラフとみなします.

2-CSPの制約グラフ

以下を満たす$G=((V,E),\Sigma,\mathcal{C})$制約グラフと呼ぶ:

  • $(V,E)$構造グラフと呼ばれる無向グラフであり, $V$は変数の集合に対応する. 頂点集合$V$$V=\{v_1,\dots,v_n\}$などと番号付けされており, それに基づいて順序が定まっている.
  • $\Sigma$は有限集合であり, アルファベットと呼ばれる. 変数には$\Sigma$の要素が代入される.
  • 各辺$e\in E$には制約と呼ばれる集合$c(e)\subseteq \Sigma\times \Sigma$が対応しており, $(a,b)\in\Sigma\times\Sigma$$(a,b)\in c(e)$を満たすとき, $(a,b)$は制約$c(e)$を満たすという.

関数$\sigma\colon V\to \Sigma$割当といい,
$$ \UNSAT(G,\sigma)=\frac{|\{uv\in E\colon (\sigma(u),\sigma(v))\not\in c(uv)\}|}{|E|} $$
を割当$\sigma$によって充足されない制約の割合とし, $\UNSAT(G)=\min\{\UNSAT(G,\sigma)\colon \sigma\in \Sigma^V\}$とする. ここで$\{u,v\}$$u$$v$よりも($V$上の順序の意味で)前にあり$(\sigma(u),\sigma(v))$を順序対として扱っている.

構造グラフという用語は元論文ではunderlying graphと呼ばれているため適切な和訳ではないのですが, 意味合いとしては適当かと思いこのように読んでいます.

上で定義した$\UNSAT$は2-CSPに限ると 前回の記事 で定義した$\UNSAT$と一致します. 例えば$\UNSAT(G)=0$ならばその2-CSPインスタンスは充足可能です. なお, 一般のk-CSPに対しても同様にして制約"ハイパー"グラフを定義できますが, ここではそれは扱いません.

例えば3彩色問題の制約グラフはインスタンスのグラフそのものになります. 2-CSPの制約グラフはその構造を表す離散構造です. 基本的にはCSPの制約の内容よりもその構造を重要視します.

2. 証明の概要

定理1は, 与えられた2-CSPのインスタンスの制約グラフを主張を満たす別の2-CSPの制約グラフに変換する方法(=アルゴリズム)を与えることによって証明されます. この変換は複数のステップからなります.

ステップ1. 構造グラフをスパースかつエクスパンダーにする

「スパース(疎)」というのはグラフの用語で, 一般に辺数が少ないことを指し, 文脈によって意味が異なってきますがここでは辺数が頂点数の線形オーダーになっていることを意味します.

ステップ1では, 任意に与えられた制約グラフを"良い"構造をもつ構造グラフに変形します. ある定数$d_0\in\Nat$に対して$(d_0+1)$-正則グラフに変換します. その後, ある定数$\lambda<1$に対して$\lambda$-エクスパンダーに変換します.

この変換によって$\UNSAT$の値は高々定数倍しか変化しないようにします.

ステップ2. UNSATの増幅

ステップ1後の制約グラフ$G_1$

  • 充足可能$\iff \UNSAT(G_1)=0$
  • 充足不可能$\iff \UNSAT(G_1)\geq 1/|E|$

が成り立ちます. 一方で定理1では二番目の不等式の下界を入力サイズに依存しない定数にする必要があります。そこで$\UNSAT(G_2)\geq 2\UNSAT(G_1)$を満たすように制約グラフ$G_2$を構成します この増幅ステップで構造グラフのエクスパンダー性とスパース性が役に立ちます. Dinurの論文Din07の技術的貢献はこのステップにあります.

実は, ステップ2の変換では$\UNSAT$の値を増大させる代わりにアルファベット$\Sigma$のサイズが増大してしまいます. 従ってステップ2の変換を$O(\log |E|)$回適用してしまうとアルファベットサイズが与えられた$G$に依存してしまうため, 定理1の主張は得られません.

アルファベットサイズの減少

ステップ2後の制約グラフ$G_2$$G_1$よりもアルファベットサイズが増大してしまうという欠点がありました. そこで, $\UNSAT$の値をほどほどに保ちつつアルファベットサイズを$\Sigma_0$にします.

全体の構成

与えられた制約グラフ$G$に対し, まずステップ1を用いてスパースかつエクスパンダーな構造グラフをもつ制約グラフに変換します. その後, ステップ2と3を$O(\log |E|)$回繰り返すことによって$\UNSAT$の値を$1/|E|$から$c$に増やします.

本記事ではステップ1のみ解説し, 次回の記事でステップ2と3を扱います.

3. ステップ1: 前処理

スパースかつエクスパンダーであるような制約グラフを持つ2-CSPを"良い"CSPであるとみなします. この節では, 任意の2-CSPのインスタンス$\mathcal{C}$を別の良い2-CSPのインスタンス$\mathcal{C}'$に変形する方法を解説します.

ある定数$\lambda<1,d\in\Nat,c>0,\beta>0$が存在して, 任意の制約グラフ$G=((V,E),\Sigma,\mathcal{C})$が与えられたときに以下の性質を満たす制約グラフ$G'=((V',E'),\Sigma,\mathcal{C}')$を出力する決定的多項式時間アルゴリズムが存在する:

  • $(V',E')$は自己ループを持つ$d$-正則な$\lambda$-エクスパンダー.
  • $|V'|\leq c|E|$.
  • $\UNSAT(G)\geq \UNSAT(G')\geq \beta\cdot \UNSAT(G)$.

この定理の証明は

  • 次数の削減
  • エクスパンダー化

の二つのステップからなります.

次数の削減

ある定数$d\in\Nat$が存在して, 任意に与えられた制約グラフ$G=((V,E),\Sigma,\mathcal{C})$を, 以下を満たす別の制約グラフ$G'=((V',E'),\Sigma,\mathcal{C}')$に変換する多項式時間アルゴリズムが存在する:

  • $(V',E')$$d$-正則
  • $|V'|= 2|E|$
  • $c\UNSAT(G)\leq\UNSAT(G')\leq \frac{\UNSAT(G)}{d}$

与えられた制約グラフを$G=((V,E),\Sigma,\mathcal{C})$とし, 変換後の制約グラフを$G'=((V',E'),\Sigma,\mathcal{C}')$と書くことにします.

元のグラフの各頂点$v\in V$に対し, $[v]=\{(v,e)\colon v\in e\}$とします. すなわち$v$とそれに接続する辺$e$の組からなる集合です. 新しいグラフの頂点集合$V'$$V'=\bigcup_{v\in V}[v]$とします.

直感的には, 元のグラフの各頂点$v$に対しそれを$\deg(v)$個にコピーし, それぞれのコピーに接続辺$e$のラベルを一個ずつ付与したものを新たな頂点としています.
なお, 元の制約グラフが自己ループ$vv$を含む場合, $[v]$$(v,vv)$を二つ含む(つまり多重集合になる)とします. このようにすることによって, 各辺$uv$に対して二つの頂点$(u,uv),(v,uv)$が生成されるので, $|V'|=2|E|$が成り立ちます (なお, 自己ループを一つの頂点として$[v]$を定義した場合でも同じ証明が回るので問題ありません).

次に新しいグラフの辺集合$E'$を次の定義します.

  1. 定理2を用いて各$v\in V$に対して$[v]$を頂点集合とした$\deg(v)$-頂点$d_0$-正則$\lambda_0$-エクスパンダーグラフ$X_v$を構成します. このステップで追加された辺を内部辺と呼び, 等号制約$\{(a,b)\in \Sigma^2\colon a=b\}$を付与します.

  2. 同じ辺ラベルを持つ二つの$V'$の頂点$(u,uv),(v,uv)$の間に辺を追加します. このステップで追加された辺$\{(u,uv),(v,uv)\}$を外部辺と呼び, 元の制約グラフの辺$uv$の制約$c(uv)$を付与します.

上記の二つのステップで構成された辺集合を$E'$と定めます.

!FORMULA[185][1141952][0]の構造グラフのイメージ図. $G'$の構造グラフのイメージ図.

図からすぐわかるように, ステップ2で追加された辺は$V'$上のマッチングになっています. 図では$d_0=2$としたときの例になっていますが, 定理2の$d_0$の値によっては, 例えば6-正則3頂点グラフなどを考えることもありますが, その際は多重辺や自己ループを適当につけることにします.

定義より構造グラフ$(V',E')$$(d_0+1)$-正則グラフになっています. 頂点数は$|V'|=2|E|$で, 辺数は$|E'|=\frac{|V'|(d_0+1)}{2}=(d_0+1)|E|$です. 次に$\UNSAT(G')$の値を評価します.

$\UNSAT(G,\sigma)=\UNSAT(G)$を達成する割当を$\sigma\in\Sigma^V$とします. $G'$の割当$\sigma'\colon V'\to \Sigma$$\sigma'(v,e)=\sigma(v)$で定めます.
$\sigma'$は内部辺の等号制約を全て満たすので, 充足されない辺の本数は$\sigma$のそれと一致します. よって
\begin{align*} \UNSAT(G')\leq \UNSAT(G',\sigma') = \frac{|E|\UNSAT(G,\sigma)}{(d_0+1)|E|} = \frac{1}{d_0+1}\cdot \UNSAT(G) \end{align*}
を得ます.

次に$\UNSAT(G')$の下界, すなわち, ある($G$に依存しない)定数$c>0$に対して$\UNSAT(G',\sigma')\geq c\cdot \UNSAT(G,\sigma)$を満たすことを示します.
$\sigma'\colon V'\to\Sigma$$\UNSAT(G',\sigma')=\UNSAT(G)$を達成する$G'$の割当とし, 各$v\in V$に対して$\sigma(v)=$$W_v$内の$\sigma'(\cdot)$の値の中での多数決」, すなわち
\begin{align*} \sigma(v) = \argmax_{a\in\Sigma}\left\{\Pr_{i\sim W_v}[\sigma'(i)=a]\right\} \end{align*}
とします. $F\subseteq E$を, $G$の辺であって$\sigma$によって充足されないものの集合とし, $F'\subseteq E'$を同様に$G'$の辺であって$\sigma'$によって充足されないものの集合とします. つまり$\UNSAT(G',\sigma')=\frac{|F'|}{|E|}$, $\UNSAT(G,\sigma)=\frac{|F|}{|E|}$です.
$S\subseteq V'$を多数決によって意見が採用されなかった頂点の集合, すなわち
$$ S = \{(v,e)\in V'\colon \sigma'(v,e) \neq \sigma(v)\} $$
とします.

ここで, 以下の二つのケースを考えます:

ケース1. $|S|\geq \frac{\UNSAT(G,\sigma)}{2}|E|$の場合.

$v\in V,a\in\Sigma$に対して$S^v=[v]\cap S$, $S^v_a = \{(v,e)\in S^v\colon \sigma'(v,e)=a\}$とします. なお, 意見$a$が多数決で採用されている場合(つまり$\sigma(v)=a$の場合)は$S^v_a=\emptyset$であり, そうでない場合は過半数をとれていないはずなので$|S^v_a|\leq \frac{|[v]|}{2}$が成り立ちます.

!FORMULA[232][36074054][0]内の各頂点!FORMULA[233][-1154055162][0]は意見!FORMULA[234][567036092][0]を持ち, その多数決によって!FORMULA[235][-122423082][0]を定める. 多数決にならなかった頂点!FORMULA[236][-1154055162][0]の集合(=青い領域)を!FORMULA[237][37205][0]とする. $[v]$内の各頂点$(v,e)$は意見$\sigma'(v,e)$を持ち, その多数決によって$\sigma(v)$を定める. 多数決にならなかった頂点$(v,e)$の集合(=青い領域)を$S$とする.

そこで$[v]$内部のグラフ$X_v$とその頂点部分集合$S^v_a$に対して定理3(エクスパンダー混交補題)を適用することによって,
$$ |E(S^v_a,[v]\setminus S^v_a)| \geq \frac{(1-\lambda)d_0}{2}|S^v_a| $$
を得ます. この式の左辺は$S^v_a$とその外側をつなぐ内部辺の本数を意味しますが, これらの辺は$G'$において, 内部辺の等号制約を満たしていないはずであり, すなわち$F'$に属すので
\begin{align*} |F'|\geq \frac{1}{2}\sum_{v,a}|E(S^v_a,[v]\setminus S^v_a)| \geq \frac{(1-\lambda_0)d_0}{4}|S| \end{align*}
により, $|S|$の仮定から
$$ \UNSAT(G')\geq \frac{(1-\lambda_0)d_0}{8(d_0+1)}\cdot \UNSAT(G) $$
を得ます.

ケース2. $|S|< \frac{\UNSAT(G,\sigma)}{2}|E| $の場合.

任意の辺$e=uv\in F$に対して, その両端点が多数決で意見が変わらなかったならば, $E'$の辺$\{(u,e),(v,e)\}$もまた$F'$に属しているはずです. 一方でそうでなかったならば$(u,e)$または$(v,e)$の少なくとも一方が$S$に属します. すなわち
$$ |F|\leq |F'|+|S| $$
が成り立ちます. ここから
\begin{align*} |F'|&\geq |F|-|S| \\ &\geq |E|\cdot\UNSAT(G) - \frac{\UNSAT(G)}{2}|E| \\ &= \frac{1}{2(d_0+1)}\UNSAT(G)\cdot |E'| \end{align*}
を得ます.

以上より, $c=\min\left\{\frac{(1-\lambda_0)d_0}{8(d_0+1)},\frac{1}{2(d_0+1)}\right\}$に対して$\UNSAT(G')\geq c\UNSAT(G)$を得ます.

エクスパンダー化

ある定数$\lambda<1,d,d_0\in\Nat$が存在して, 構造グラフが$d$-正則であるような制約グラフ$G=((V,E),\Sigma,\mathcal{C})$が与えられたとき, それを以下を満たす別の制約グラフ$G'=((V',E'),\Sigma,\mathcal{C}')$に変換する多項式時間アルゴリズムが存在する:

  • 構造グラフ$(V,E')$$(d+d_0+2)$-正則$\lambda$-エクスパンダーであり, 各頂点は自己ループを持つ.
  • $\UNSAT(G')=\frac{d}{d+d_0+2}\UNSAT(G)$

与えられた制約グラフを$G=((V,E),\Sigma,\mathcal{C})$とし, 変換後の制約グラフを$G'=((V',E'),\Sigma,\mathcal{C}')$と書くことにします.

$G'$の構成は簡単です.

  1. 頂点集合$V$上の$d_0$-正則$\lambda_0$エクスパンダーを構成してその辺集合を$E$に追加する (多重辺を許す).
  2. 各頂点に対して自己ループを付与する.
  3. ステップ1,2で追加された辺$e$には常に充足される自明な制約$c(e)=\Sigma\times \Sigma$を付与する.

元のグラフ$(V,E)$$d$-正則ならば, $G'$の構造グラフは$(d+d_0+2)$-正則になります (自己ループの辺の次数は2つ分にカウントしている).

$\sigma,\sigma,\colon V\to \Sigma$をそれぞれ$G,G'$の割当とします. 追加された辺は全て自明な制約しか付与されていないので, 充足されなかった辺の本数は$G,G'$で一致します.
よって$|E|\UNSAT(G)=|E'|\UNSAT(G')$なので
$$ \UNSAT(G') = \frac{|E|}{|E'|}\UNSAT(G) = \frac{d}{d+d_0+2}\UNSAT(G) $$
を得ます.

最後に$(V,E')$のエクスパンダー性を示します.
$A,A'$をそれぞれ$(V,E),(V,E')$の隣接行列とし, $B$をステップ1で追加したエクスパンダーグラフの隣接行列とし, $I$を単位行列とします. $(V,E')$の定義より$A'=A+B+2I$です (自己ループの次数が2としてカウントされているので$2I$になっています). 対称行列$M$の固有値が$\lambda_1\geq \dots\geq \lambda_n$のとき, $\lambda(M)=\max\{\lambda_2,|\lambda_n|\}$とします. 第二固有値に関するmin-max定理(Courant–Fischerの最大最小定理)より,
\begin{align*} \lambda(A') \leq \max_{\|x\|=1,x\bot \indicator=0}|x^\top A' x| \leq \lambda(A) + \lambda(B) + 2\lambda(I) \leq d + \lambda_0 d_0 + 2 \end{align*}
より, $P'=\frac{1}{d+d_0+2}A'$$(V,E')$の遷移確率行列とすると
$$ \lambda(P') \leq \frac{d+\lambda_0 d_0+2}{d+d_0+2} $$
となります. すなわち, $\lambda:=\frac{d+\lambda_0 d_0+2}{d+d_0+2}<1$に対して$(V,E')$$\lambda$-エクスパンダーです.

定理4の証明

$G=((V,E),\Sigma,\mathcal{C})$を与えられた制約グラフとします. 補題5のアルゴリズムを用いて構造グラフ$d$-正則にし, さらに補題6のアルゴリズムを用いて$\lambda$-エクスパンダーにします. 最終的に得られるグラフは正則性やエクスパンダー性を満たしており, $\UNSAT$の値はそれぞれの補題で定数倍しか変化しません.

付録

(Courant–Fischerの最大最小定理)

$n$次対称行列$A\in\Real^{n\times n}$の固有値を$\lambda_1\geq \dots\geq\lambda_n$とすると, 任意の$k=1,\dots,n$に対して
$$ \lambda_k = \max_{S\colon \dim S=k} \min_{x\in S\setminus\{0\}} \frac{x^\top A x}{\|x\|^2}. $$
ただし, $S\subseteq \Real^n$は次元$k$の任意の部分空間を動く.

参考文献

投稿日:2023820
更新日:815
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

knewknowl
knewknowl
21
5721
東工大助教. 理論計算機科学.

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中