| dbo:abstract
|
- En teoria de la complexitat, el Teoremoa de Savitch, provat per Walter Savitch el 1970 dona la relació entre complexitats espacials deterministes i no deterministes. Diu que per cada funció Dit d'altre manera, si una màquina de Turing no determinista pot resoldre un problema usant un espai f(n), una màquina de Turing ordinària (determinista) pot resoldre el mateix problema amb el quadrat del dit espai. (ca)
- في نظرية التعقيد الحسابي مبرهنة سافيتش هي نتيجة اساسية مهمة تحدد العلاقة بين تعقيد المساحة القطعي وغير القطعي. ونص المبرهنة هو: في حين أنَّ ((NSPACE(s(n هو قسم كل اللغات التي يمكن تقريرها بواسطة آلة تيورنج غير قطعية التي تستغل (s(n مساحة اضافية على الأكثر، ((SPACE(s(n هو قسم كل اللغات التي يمكن تقريرها بواسطة آلة تيورنج قطعية التي تستغل (s(n مساحة اضافية على الأكثر. (ar)
- Der Satz von Savitch oder Theorem von Savitch ist ein Satz aus der Komplexitätstheorie, der 1970 von Walter Savitch bewiesen wurde. Er besagt, dass ein von einer nichtdeterministischen Turingmaschine mit einer bestimmten Platzkomplexität lösbares Problem auf einer deterministischen Turingmaschine mit einer quadratisch höheren Platzschranke gelöst werden kann. Eine Folgerung aus dem Satz von Savitch ist die Gleichheit von PSPACE und NPSPACE. (de)
- En teoría de la complejidad computacional, el teorema de Savitch establece que: Como corolario, se tiene que PSPACE = NPSPACE. (es)
- 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 , In other words, if a nondeterministic Turing machine can solve a problem using 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 (as formalized in the unproven exponential time hypothesis), Savitch's theorem shows that it has a markedly more limited effect on space requirements. (en)
- Nella teoria della complessità computazionale, il teorema di Savitch, dimostrato da Walter Savitch nel 1970, afferma che per ogni funzione : . In altre parole, se una macchina di Turing non deterministica è in grado di risolvere un problema in spazio f(n), una macchina di Turing deterministica può risolvere lo stesso problema nel quadrato dello spazio. Un importante corollario del teorema è che PSPACE = . Ciò deriva dal fatto che il quadrato di una funzione polinomiale è a sua volta una funzione polinomiale. (it)
- Le théorème de Savitch est un théorème de théorie de la complexité, un domaine de l'informatique théorique. Il a été prouvé par Walter Savitch en 1970 et donne une relation entre les classes de complexité en espace, déterministes et non-déterministes. Une conséquence importante est que NPSPACE = PSPACE, c'est-à-dire, tout problème décidable sur une machine non-déterministe en espace polynomial, l'est aussi sur une machine déterministe en espace polynomial. (fr)
- サヴィッチの定理（英: Savitch's theorem）とは、1970年にウォルター・サヴィッチが証明した計算量理論における定理である。f(n) ≥ log(n) であるような任意の関数 f について、次が成り立つとするものである。 NSPACE(f(n)) ⊆ DSPACE(f²(n)). 言い換えれば、非決定性チューリング機械が f(n) の領域を使ってある問題を解けるとき、通常の決定性チューリング機械は同じ問題をその平方の領域を使って解ける。時間は非決定性によって指数関数的に短縮されると考えられるが、この定理によれば、領域の効率化は明らかにそれよりも限定的である。 (ja)
- 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. (pt)
- Теорема (1970): NSPACE(f(n)) ⊆ (f²(n)). То есть, если недетерминированная машина Тьюринга может решить проблему используя f(n) памяти, то детерминированная машина Тьюринга сможет это сделать за квадрат памяти. (ru)
- 萨维奇定理（英語：Savitch's theorem）是计算复杂性理论中的一个定理，由于1970年证明。定理的结论为对于任何函数满足，下列关系成立： 亦即，如果一台非确定型图灵机能够利用空间解决某个问题，那么一台确定型图灵机能够在至多空间解决相同的问题。尽管非确定性的引入能够在时间上带来指数的提升，但是，这种引入对于空间而言作用有限。 (zh)
- Теорема Севіча з теорії складності обчислень, доведена у 1970 році, дає зв’язок між детермінованою та недетермінованою складністю простору . У ньому зазначено, що для будь-якої функції , Іншими словами, якщо недетермінована машина Тюрінга може вирішити проблему, використовуючи пам'яті, детермінована машина Тюрінга може вирішити ту ж задачу за квадрат пам'яті. Хоча здається, що не детермінізм може призвести до експоненційного виграшу в часі, але ця теорема показує, що він має помітно більш обмежений вплив на вимоги до пам'яті. (uk)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 8293 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- En teoria de la complexitat, el Teoremoa de Savitch, provat per Walter Savitch el 1970 dona la relació entre complexitats espacials deterministes i no deterministes. Diu que per cada funció Dit d'altre manera, si una màquina de Turing no determinista pot resoldre un problema usant un espai f(n), una màquina de Turing ordinària (determinista) pot resoldre el mateix problema amb el quadrat del dit espai. (ca)
- في نظرية التعقيد الحسابي مبرهنة سافيتش هي نتيجة اساسية مهمة تحدد العلاقة بين تعقيد المساحة القطعي وغير القطعي. ونص المبرهنة هو: في حين أنَّ ((NSPACE(s(n هو قسم كل اللغات التي يمكن تقريرها بواسطة آلة تيورنج غير قطعية التي تستغل (s(n مساحة اضافية على الأكثر، ((SPACE(s(n هو قسم كل اللغات التي يمكن تقريرها بواسطة آلة تيورنج قطعية التي تستغل (s(n مساحة اضافية على الأكثر. (ar)
- Der Satz von Savitch oder Theorem von Savitch ist ein Satz aus der Komplexitätstheorie, der 1970 von Walter Savitch bewiesen wurde. Er besagt, dass ein von einer nichtdeterministischen Turingmaschine mit einer bestimmten Platzkomplexität lösbares Problem auf einer deterministischen Turingmaschine mit einer quadratisch höheren Platzschranke gelöst werden kann. Eine Folgerung aus dem Satz von Savitch ist die Gleichheit von PSPACE und NPSPACE. (de)
- En teoría de la complejidad computacional, el teorema de Savitch establece que: Como corolario, se tiene que PSPACE = NPSPACE. (es)
- Nella teoria della complessità computazionale, il teorema di Savitch, dimostrato da Walter Savitch nel 1970, afferma che per ogni funzione : . In altre parole, se una macchina di Turing non deterministica è in grado di risolvere un problema in spazio f(n), una macchina di Turing deterministica può risolvere lo stesso problema nel quadrato dello spazio. Un importante corollario del teorema è che PSPACE = . Ciò deriva dal fatto che il quadrato di una funzione polinomiale è a sua volta una funzione polinomiale. (it)
- Le théorème de Savitch est un théorème de théorie de la complexité, un domaine de l'informatique théorique. Il a été prouvé par Walter Savitch en 1970 et donne une relation entre les classes de complexité en espace, déterministes et non-déterministes. Une conséquence importante est que NPSPACE = PSPACE, c'est-à-dire, tout problème décidable sur une machine non-déterministe en espace polynomial, l'est aussi sur une machine déterministe en espace polynomial. (fr)
- サヴィッチの定理（英: Savitch's theorem）とは、1970年にウォルター・サヴィッチが証明した計算量理論における定理である。f(n) ≥ log(n) であるような任意の関数 f について、次が成り立つとするものである。 NSPACE(f(n)) ⊆ DSPACE(f²(n)). 言い換えれば、非決定性チューリング機械が f(n) の領域を使ってある問題を解けるとき、通常の決定性チューリング機械は同じ問題をその平方の領域を使って解ける。時間は非決定性によって指数関数的に短縮されると考えられるが、この定理によれば、領域の効率化は明らかにそれよりも限定的である。 (ja)
- 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. (pt)
- Теорема (1970): NSPACE(f(n)) ⊆ (f²(n)). То есть, если недетерминированная машина Тьюринга может решить проблему используя f(n) памяти, то детерминированная машина Тьюринга сможет это сделать за квадрат памяти. (ru)
- 萨维奇定理（英語：Savitch's theorem）是计算复杂性理论中的一个定理，由于1970年证明。定理的结论为对于任何函数满足，下列关系成立： 亦即，如果一台非确定型图灵机能够利用空间解决某个问题，那么一台确定型图灵机能够在至多空间解决相同的问题。尽管非确定性的引入能够在时间上带来指数的提升，但是，这种引入对于空间而言作用有限。 (zh)
- Теорема Севіча з теорії складності обчислень, доведена у 1970 році, дає зв’язок між детермінованою та недетермінованою складністю простору . У ньому зазначено, що для будь-якої функції , Іншими словами, якщо недетермінована машина Тюрінга може вирішити проблему, використовуючи пам'яті, детермінована машина Тюрінга може вирішити ту ж задачу за квадрат пам'яті. Хоча здається, що не детермінізм може призвести до експоненційного виграшу в часі, але ця теорема показує, що він має помітно більш обмежений вплив на вимоги до пам'яті. (uk)
- 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 , (en)
|
| rdfs:label
|
- مبرهنة سافيتش (ar)
- Teorema de Savitch (ca)
- Satz von Savitch (de)
- Teorema de Savitch (es)
- Théorème de Savitch (fr)
- Teorema di Savitch (it)
- サヴィッチの定理 (ja)
- Savitch's theorem (en)
- Teorema de Savitch (pt)
- Теорема Сэвича (ru)
- 萨维奇定理 (zh)
- Теорема Севіча (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is dbp:knownFor
of | |
| is foaf:primaryTopic
of | |
