T
Peu commune
Théorème de Savitch
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.
Extrait raccourci de l'article Wikipédia, CC BY-SA 4.0.