Notions importantes

    Il existe deux types de RAM :

• La RAM déterministe (simplement appellée RAM)
• La RAM non déterministe (ou NRAM)

Une RAM est matétiellement constituée :

• de registres d'entrées
• d'une section de travail (ou mémoire principale)

    On va voir ici les classes de complexité non déterministe mixte temps-espace, c'est à dire pour lesquelles les ressources en temps et en espace sont restreintes simultanément.

    En effet, on remarque que pour certains problèmes, il est possible d'échanger du temps contre des ressources en espace, et inversement. On peut citer par exemple :

• le problème du tri pour lequel on connait des algorithmes en temps quadratiques et en espace constant O(1) (tri-selection ou tri-insertion)
• des algorithmes en temps constance O(n) et en espace constant O(n) (tri par paquets).
• etc.