Back مبرهنة سافيتش Arabic Teorema de Savitch Catalan Satz von Savitch German Savitch's theorem English Teorema de Savitch Spanish Théorème de Savitch French משפט סביץ' HE Teorema di Savitch Italian サヴィッチの定理 Japanese Теорема Сэвича Russian
Na teoria da complexidade computacional, o teorema de Savitch, provado por Walter Savitch em 1970, afirma que para toda função ƒ(n) ≥ log(n),
NSPACE(ƒ(n)) ⊆ DSPACE((ƒ(n))²).
em outras palavras, se uma máquina de Turing não-determinística pode resolver um problema usando um espaço f(n) (polinomial), uma máquina de Turing determinística ordinária pode resolver o mesmo problema dentro dessa região delimitada. Embora não-determinismo possa produzir aumento exponencial de tempo, esse teorema mostra que o mesmo não ocorre na requisição de espaço.