よく使う記法

• 自然数$n\in \mathbb{N}$に対して$[n]={1,\dots,n}$とします.
• 有限集合$S$に対し, $x\sim S$と書いたとき, 要素$x$は$S$上一様ランダムに選ばれることを意味します.
  • 例えば$\Pr_{x\sim S}[\cdot]$と書くと, $S$上一様ランダムに選ばれた$x$に関する確率を考えることを意味します.
• より一般に, 有限集合上の分布$\nu$に対し, $x\sim \nu$と書くと$x$は分布$\nu$に従って選ばれたことを意味します.
• 確率変数$X$に対して$\supp(X) = \{ x\colon \Pr[X=x]>0 \}$を$X$の台(サポート)といいます (基本的には$X$として離散的な値をとるもののみを考えます).
• アルゴリズム$\mathcal{A}$と入力$x$に対し, $\mathcal{A}(x)$はアルゴリズム$\mathcal{A}$の入力$x$に対する出力を表すことにします.
  • $\mathcal{A}$が乱択アルゴリズムの場合は$\mathcal{A}(x)$は確率変数として扱われます.
• グラフ$G=(V,E)$とは有限集合$V$と$E\subseteq\binom{V}{2}$のペアです.
  • 頂点$u\in V$の隣接点集合を$N(u)\subseteq V$で表します.