FANDOM


欲張りクリーク列 (Greedy clique sequences) は、Harvey Friedman が 2010年に定義した、グラフ理論による3つの急増加する関数を生み出す概念である[1]。フリードマンが定義した関数の中では最強の部類である。

定義 編集

用語と記法 編集

  1. クリーネ閉包を使って、\(\mathbb{Q}^*\) はすべての有理数のタプル、すなわちQ組 (Q-tuple) の集合を意味するものとする。タプルに1からインデックスをつけて下付き文字で記す。
  2. タプルの連結を角括弧であらわす。たとえば\(\langle (0,1), (2,3) \rangle = (0,1,2,3)\) である。
  3. \(a \in \mathbb{Q}^*\) に対して、\(a\) の上シフト \(\text{us}(a)\) を、\(a\) のすべての負ではない要素に1を加えたものであると定義する[2]
  4. \(a,b \in \mathbb{Q}^*\) に対して、2項演算 \(\preceq\) と \(\prec\) を \(a \preceq b \Leftrightarrow \max(a) \leq \max(b)\) 及び \(a \prec b \Leftrightarrow \max(a) < \max(b)\) によって定義する。
  5. \(a,b \in \mathbb{Q}^*\) が順序等価 (order equivalent) であるとは、\(a\) と \(b\) が同じ長さであり、かつすべての \(i\) と \(j\) に対して \(a_i < a_j \Leftrightarrow b_i < b_j\) であることを意味する。
  6. 集合 \(E \subseteq \mathbb{Q}^*\) が順序不変 (order invariant) であるとは、すべての順序等価な \(x\) と \(y\) に対して \(x \in E \Leftrightarrow y \in E\) であることを意味する。
  7. \(H\) を \(\mathbb{Q}^*\) の要素を頂点に持つグラフとする。集合 \(E\) を、すべての \(H\) の辺 \((x,y)\) に対して、その連結 \(\langle x, y \rangle\) を \(E\) の要素とするような集合とする。\(E\) が順序不変であるとき、\(H\) は順序不変であるとする。\(H\) が順序不変のとき、\(H\) は無限の辺を持つ。
  8. 無向グラフ \(G\) の部分グラフ \(A\) が \(G\) のクリークであるとは、すべての \(x,y \in A\) に対して、\((x, y)\) が \(G\) の辺であるという意味である。
  9. 有向グラフ \(G\) の部分グラフ \(A\) が \(G\) の下降クリークであるとは、すべての \(x \succ y\) を満たす \(x,y \in A\) に対して、\((x, y)\) が \(G\) の辺であるという意味である[2]

欲張りクリーク列とスレッド 編集

タプルの集合 \(S \subseteq \mathbb{Q}^*\) に対して、列 \(\mathbf{x}\) をタプル \(x_i \in S\) に対する空ではないタプル \((x_1, x_2, \ldots, x_n)\) とする。これは \(\mathbb{Q}\) のタプルではなく、\(\mathbb{Q}\) のタプルのタプルである。

\(S\) の要素を頂点に持つ単純グラフ \(G\) の上シフト欲張りクリーク列 (upper shift greedy clique sequence を略して USGCS) \(\mathbf{x}\) は、以下のすべてが成立している列である。

  1. \(x_1\) は 0 のみである。
  2. \(m\) を \(2 \leq 2m \leq n - 1\) を満たす正の整数であるとする。\(Y\) を\(\langle x_1,x_2,\ldots, x_{2m-1}\rangle\) の連結とし、\(y = (Y_m, Y_{m+1}, \ldots, Y_{m+k-1})\) とする (\(k \in \mathbb{N}\))。
    1. \(x_{2m} \preceq y\) かつ \((y, 2m)\) は \(G\) の辺ではない。
    2. \(x_{2m + 1} = \text{us}(x_{2m})\)
  3. \(\{x_2, x_3, \ldots, x_n\}\) が \(G\) のクリークである。

\(S\) の要素を頂点に持つ有向グラフ \(G\) の上シフト欲張り下降クリーク列 (upper shift greedy down clique sequence を略して USGDCS) \(\mathbf{x}\) は、以下のすべてが成立している列である。

  1. \(x_1\) は 0 のみである。 
  2. \(m\) と \(y\) を上と同様に定義する。
    1. 「\(x_{2m} = y\)」あるいは「\(x_{2m} \prec y\) かつ \((y, 2m)\) は\(G\) の辺ではない」
    2. \(x_{2m+1} = \text{us}(x_{2m})\)
  3. \(\{x_2, x_3, \ldots, x_n\}\) が \(G\) の下降クリークである。

\(\mathbf{x}\) のスレッドは、\((1,2,...,n)\) の部分列 \((u_1, u_2, \ldots, u_r)\) で、以下のように帰納的に定義される。

  1. \(u_1 = 1\)
  2. \(u_i\) が定義されている時に、\(u_{i+1}\) を次のように決める。\(j \in [u_i, 2^{u_i}]\) の中で、\(x_j \prec x_{u_i}\) が成立するような \(j\) を選ぶ(そのような \(j\) が存在しなければ \(u_{i+1}\) は定義されない)。そのような \(j\) が複数あるときには、その中で \(\max(x_j)\) が最大の \(j\) を選ぶ。そのような \(j\) が複数あるときには、その中で最大の \(j\) を選ぶ。そして、\(u_{i+1} = j\) とする。

スレッド \(u\) について \(2^{u_r} \leq n\) の時に、そのスレッドは開いたスレッドであるとする。つまり、\(u_{r+1}\) を \(j \in [u_r, 2^{u_r}]\) の範囲でフルに探したけれどみつからなかった、ということである。

  • \(G\) の上シフト欲張りクリーク列 \(\mathbf{x}\) が、開いたスレッド \(u\) を持つ時に、\(\mathbf{x}\) は \(G\) の開放上シフト欲張りクリーク列であるとする。
  • \(G\) の上シフト欲張り下降クリーク列 \(\mathbf{x}\) が、開いたスレッド \(u\) を持つ時に、\(\mathbf{x}\) は \(G\) の開放上シフト欲張りクリーク下降列であるとする。

欲張りクリーク関数 編集

以下の急増加する関数を定義する。

  • \(\text{USGCS}(k)\) は、\(S = \mathbb{Q}^k\) としたときに「\(S\) の要素を頂点に持つすべての順序不変な単純グラフ \(G\) が、最大でも \(N\) の長さの開放上シフト欲張りクリーク列を持っている」と言える最小の整数 \(N\) である。
  • \(\text{USGDCS}(k)\) は、\(S = \mathbb{Q}^k\) としたときに「\(S\) の要素を頂点に持つすべての順序不変な有向グラフ \(G\) が、最大でも \(N\) の長さの開放上シフト欲張りクリーク下降列を持っている」と言える最小の整数 \(N\) である。
  • \(\text{USGDCS}_2(k)\) は、\(\text{USGDCS}(k)\) の定義において \(S = \mathbb{Q}^k \cup \mathbb{Q}^{k+1}\) としたものである。

関数の増加速度 編集

ここでは、\(n\) は自然数とする。まずは、次の理論を定義する。

  • SRP 理論は、ZFC に、すべての \(n\) に対して「\(n\)-Stationary Ramsey Property を持つラムゼイ基数 (Ramsey cardinal) が存在する」という公理を加えたものである。
  • SRP+ 理論は、ZFC に、「すべての \(n\) に対して\(n\)-Stationary Ramsey Property を持つラムゼイ基数が存在する」という公理を加えたものである。
  • HUGE 理論は、ZFC に、すべての \(n\) に対して「\(n\)-膨大基数 (\(n\)-huge cardinal) が存在する」という公理を加えたものである。
  • HUGE+ 理論は、ZFC に、「すべての \(n\) に対して \(n\)-膨大基数が存在する」という公理を加えたものである。

この時、それぞれの関数の増加速度は次のようになる。

  • USGCS と USGDCS は、SRPによって証明可能な再帰関数をすべて支配し、SRP+によって証明可能な再帰関数である。
  • USGDCS2 は、HUGEによって証明可能な再帰関数をすべて支配し、HUGE+によって証明可能な再帰関数である。

出典 編集

  1. http://www.cs.nyu.edu/pipermail/fom/2010-January/014282.html, with corrections from [1]
  2. 2.0 2.1 http://www.cs.nyu.edu/pipermail/fom/2009-December/014276.html

広告ブロッカーが検出されました。


広告収入で運営されている無料サイトWikiaでは、このたび広告ブロッカーをご利用の方向けの変更が加わりました。

広告ブロッカーが改変されている場合、Wikiaにアクセスしていただくことができなくなっています。カスタム広告ブロッカーを解除してご利用ください。

FANDOMでも見てみる

おまかせWiki