加速定理
理論 T {\displaystyle T} とその拡大理論 S {\displaystyle S} について「 T {\displaystyle T} において証明可能な論理式で S {\displaystyle S} においてはより簡単に証明できるものが存在する」という形の定理は、計算複雑性に関する加速定理の類比として、同じく加速定理と呼ばれる。その代表的なものとしてはゲーデルの加速定理がある。これら異なるタイプの加速定理の間には或る種の対応が存在する。例えば、ブラムの加速定理の変種であるハルトマニスの加速定理を用いてゲーデルの加速定理が証明できることが知られている。また、エーレンフォイヒト・ミッシェルスキーの加速定理は、帰納的可算集合の加速可能性に関するある事実を用いて証明できる。