Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Savitch's_theorem> ?p ?o. }
Showing items 1 to 38 of
38
with 100 items per page.
- Savitch's_theorem abstract "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 ƒ(n) ≥ log(n),In other words, if a nondeterministic Turing machine can solve a problem using f(n) space, an ordinary 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, this theorem shows that it has a markedly more limited effect on space requirements.".
- Savitch's_theorem wikiPageExternalLink foundations-of-complexity-lesson-18.html.
- Savitch's_theorem wikiPageExternalLink savitchs-theorem.
- Savitch's_theorem wikiPageID "658501".
- Savitch's_theorem wikiPageRevisionID "584421611".
- Savitch's_theorem hasPhotoCollection Savitch's_theorem.
- Savitch's_theorem subject Category:Structural_complexity_theory.
- Savitch's_theorem subject Category:Theorems_in_computational_complexity_theory.
- Savitch's_theorem type Abstraction100002137.
- Savitch's_theorem type Communication100033020.
- Savitch's_theorem type Message106598915.
- Savitch's_theorem type Proposition106750804.
- Savitch's_theorem type Statement106722453.
- Savitch's_theorem type Theorem106752293.
- Savitch's_theorem type TheoremsInDiscreteMathematics.
- Savitch's_theorem comment "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 ƒ(n) ≥ log(n),In other words, if a nondeterministic Turing machine can solve a problem using f(n) space, an ordinary deterministic Turing machine can solve the same problem in the square of that space bound.".
- Savitch's_theorem label "Satz von Savitch".
- Savitch's_theorem label "Savitch's theorem".
- Savitch's_theorem label "Teorema de Savitch".
- Savitch's_theorem label "Teorema de Savitch".
- Savitch's_theorem label "Teorema di Savitch".
- Savitch's_theorem label "Théorème de Savitch".
- Savitch's_theorem label "Теорема Сэвича".
- Savitch's_theorem label "مبرهنة سافيتش".
- Savitch's_theorem label "サヴィッチの定理".
- Savitch's_theorem label "萨维奇定理".
- Savitch's_theorem sameAs Satz_von_Savitch.
- Savitch's_theorem sameAs Teorema_de_Savitch.
- Savitch's_theorem sameAs Théorème_de_Savitch.
- Savitch's_theorem sameAs Teorema_di_Savitch.
- Savitch's_theorem sameAs サヴィッチの定理.
- Savitch's_theorem sameAs Teorema_de_Savitch.
- Savitch's_theorem sameAs m.030dbh.
- Savitch's_theorem sameAs Q954210.
- Savitch's_theorem sameAs Q954210.
- Savitch's_theorem sameAs Savitch's_theorem.
- Savitch's_theorem wasDerivedFrom Savitch's_theorem?oldid=584421611.
- Savitch's_theorem isPrimaryTopicOf Savitch's_theorem.