Savitch's theorem
id:
savitch-s-theorem-250-7042953
title:
Savitch's theorem
text:
In computational complexity theory, Savitch's theorem, proved by Walter Savitch in 1970, gives a relationship between deterministic and non-deterministic space complexity. It states that for any function f ∈ Ω , In other words, if a nondeterministic Turing machine can solve a problem using f space, a deterministic Turing machine can solve the same problem in the square of that space bound. Although it seems that nondeterminism may produce exponential gains in time, Savitch's theorem shows that i
brand slug:
wiki
category slug:
encyclopedia
description:
Relation between deterministic and nondeterministic space complexity
original url:
https://en.wikipedia.org/wiki/Savitch%27s_theorem
date created:
date modified:
2024-02-10T12:53:33Z
main entity:
{"identifier":"Q954210","url":"https://www.wikidata.org/entity/Q954210"}
image:
fields total:
13
integrity:
14