This HTML5 document contains 64 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dbpedia-dehttp://de.dbpedia.org/resource/
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-cahttp://ca.dbpedia.org/resource/
dbpedia-eshttp://es.dbpedia.org/resource/
n8http://g.co/kg/m/
dbpedia-hehttp://he.dbpedia.org/resource/
dbpedia-trhttp://tr.dbpedia.org/resource/
dbpedia-ruhttp://ru.dbpedia.org/resource/
dbpedia-ukhttp://uk.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
category-frhttp://fr.dbpedia.org/resource/Catégorie:
dbpedia-srhttp://sr.dbpedia.org/resource/
dbpedia-pthttp://pt.dbpedia.org/resource/
n10http://fr.dbpedia.org/resource/Modèle:
wikipedia-frhttp://fr.wikipedia.org/wiki/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
dbpedia-arhttp://ar.dbpedia.org/resource/
owlhttp://www.w3.org/2002/07/owl#
n9http://ma-graph.org/entity/
dbpedia-ithttp://it.dbpedia.org/resource/
dbpedia-zhhttp://zh.dbpedia.org/resource/
dbpedia-frhttp://fr.dbpedia.org/resource/
prop-frhttp://fr.dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/
dbpedia-jahttp://ja.dbpedia.org/resource/

Statements

Subject Item
dbpedia-fr:Théorème_de_Savitch
rdfs:label
Teorema di Savitch Théorème de Savitch Теорема Севіча Satz von Savitch サヴィッチの定理 Savitch's theorem Teorema de Savitch Teorema de Savitch
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.
owl:sameAs
dbpedia-sr:Севичева_теорема dbpedia-it:Teorema_di_Savitch n8:030dbh n9:47796627 dbpedia-ja:サヴィッチの定理 dbpedia-zh:萨维奇定理 dbpedia-tr:Savitch_teoremi dbpedia-uk:Теорема_Севіча dbr:Savitch's_theorem dbpedia-pt:Teorema_de_Savitch wikidata:Q954210 dbpedia-ru:Теорема_Сэвича dbpedia-he:משפט_סביץ' dbpedia-ar:مبرهنة_سافيتش dbpedia-es:Teorema_de_Savitch dbpedia-de:Satz_von_Savitch dbpedia-ca:Teorema_de_Savitch
dbo:wikiPageID
6588904
dbo:wikiPageRevisionID
163152585
dbo:wikiPageWikiLink
dbpedia-fr:Richard_Stearns dbpedia-fr:Informatique_théorique dbpedia-fr:Classe_de_complexité dbpedia-fr:EXPSPACE category-fr:Théorème_de_la_théorie_de_la_complexité dbpedia-fr:1970_en_informatique dbpedia-fr:Complexité_en_espace dbpedia-fr:Stephen_Cook dbpedia-fr:Algorithme_récursif dbpedia-fr:Théorie_de_la_complexité_(informatique_théorique) dbpedia-fr:Logarithme dbpedia-fr:Problème_d'accessibilité dbpedia-fr:Diviser_pour_régner_(informatique) dbpedia-fr:NEXPSPACE dbpedia-fr:Juris_Hartmanis dbpedia-fr:Walter_Savitch dbpedia-fr:PSPACE dbpedia-fr:Théorème
dbo:wikiPageLength
3142
dct:subject
category-fr:Théorème_de_la_théorie_de_la_complexité
prop-fr:wikiPageUsesTemplate
n10:Article n10:Computational_Complexity_(Arora_et_Barak) n10:Palette n10:Portail
prov:wasDerivedFrom
wikipedia-fr:Théorème_de_Savitch?oldid=163152585&ns=0
prop-fr:année
1972
prop-fr:journal
Journal of Computer and System Sciences
prop-fr:nom
Savitch
prop-fr:numéro
2
prop-fr:prénom
Walter
prop-fr:titre
Relationships between nondeterministic and deterministic tape complexities
prop-fr:titreChapitre
Space complexity
prop-fr:volume
4
prop-fr:numéroChapitre
4
foaf:isPrimaryTopicOf
wikipedia-fr:Théorème_de_Savitch
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.