最終更新日：2025/12/04

(computing theory) A theorem giving a relationship between deterministic and non-deterministic space complexity.

音声機能が動作しない場合はこちらをご確認ください

正解を見る

Savitch's theorem

元となった辞書の項目

Savitch's theorem

(computing theory) A theorem giving a relationship between deterministic and non-deterministic space complexity.

日本語の意味

計算理論における定理で、決定性空間計算と非決定性空間計算の間の関係性、すなわち非決定性空間を決定性空間にシミュレートできることを示す結果を表す。

Savitch's theorem shows that nondeterministic space can be simulated deterministically with only a quadratic increase in space.

決定性空間計算量と非決定性空間計算量の関係を示す定理は、非決定性の空間を決定性でシミュレートする際に必要な空間が二乗程度にしか増えないことを示している。

意味（1）

(computing theory) A theorem giving a relationship between deterministic and non-deterministic space complexity.