b"\n_START_ARTICLE_\nTeorema de Savitch\n_START_PARAGRAPH_\nEn teoria de la complexitat, el Teoremoa de Savitch, provat per Walter Savitch el 1970 dona la relaci\xc3\xb3 entre complexitats espacials deterministes i no deterministes. Diu que per cada funci\xc3\xb3 _NEWLINE_Dit d'altre manera, si una m\xc3\xa0quina de Turing no determinista pot resoldre un problema usant un espai f(n), una m\xc3\xa0quina de Turing ordin\xc3\xa0ria (determinista) pot resoldre el mateix problema amb el quadrat del dit espai."