Karp–Flatt 指標

命題 3.3（「並列化と GPU」§3）・ ✓公理まで証明済み

$p \ge 2$ と $S \gt 0$ に対し

e(p) = \frac{\dfrac{1}{S(p)} - \dfrac{1}{p}}{1 - \dfrac{1}{p}}

とおく。所要時間が、逐次割合 $f \in [0,1]$ とオーバーヘッドの割合 $\omega(p) \ge 0$ を使って

T(p) = T(1)\Bigl(f + \frac{1-f}{p} + \omega(p)\Bigr)

と書けるとき、次が成り立つ。

$e(p) = f + \dfrac{p}{p-1}\,\omega(p)$ 。
$e(p) = f$ であることと、 $\omega(p) = 0$ 、すなわち $S(p) = 1/\bigl(f + (1-f)/p\bigr)$ であることは同値。
$2 \le p \lt p'$ で $e(p) \lt e(p')$ ならば $\omega(p) \lt \omega(p')$ 。

閉包の状態

✓ 公理まで証明済み

証明が使う定理を前提としてたどると、Rikai の中の証明だけで定義・公理（物理では基本仮定）までつながっています。

印の意味: ✓公理まで証明済み・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は閉包の状況。

証明は Rikai の他の定理を参照していません（定義と論理だけで示されています）。

証明で明示的に参照している定理は、まだありません。