| Property |
Value |
| dbo:abstract
|
- 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)
- 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)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 3142 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
| |
| prop-fr:journal
|
- Journal of Computer and System Sciences (fr)
- Journal of Computer and System Sciences (fr)
|
| prop-fr:nom
|
- Savitch (fr)
- Savitch (fr)
|
| prop-fr:numéro
| |
| prop-fr:numéroChapitre
| |
| prop-fr:prénom
| |
| prop-fr:titre
|
- Relationships between nondeterministic and deterministic tape complexities (fr)
- Relationships between nondeterministic and deterministic tape complexities (fr)
|
| prop-fr:titreChapitre
|
- Space complexity (fr)
- Space complexity (fr)
|
| prop-fr:volume
| |
| prop-fr:wikiPageUsesTemplate
| |
| dct:subject
| |
| rdfs:comment
|
- 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)
- 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)
|
| rdfs:label
|
- Satz von Savitch (de)
- Savitch's theorem (en)
- Teorema de Savitch (ca)
- Teorema de Savitch (es)
- Teorema di Savitch (it)
- Théorème de Savitch (fr)
- Теорема Севіча (uk)
- サヴィッチの定理 (ja)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
