Le non determinisme du systeme NRAM nous facilite grandement la vie.
La classe NTISP est forte dans le sens ou elle est basee sur un systeme puissant et contient quand meme un grand nombre d'algorithmes utilises regulierement (tri, etc)
De plus, le fait de classer un probleme par sa complexite en temps mais aussi en espace permet de se rapprocher plus de la reprensentation informatique que l'on se fait en tant que developpeur.
On appelle NTISP-sigma (T(n), S(n)) la classe des sigma-problemes calculables sur une NRAM en temps T(n) et en espace S(n).
Nous disposons en entree :
Le probleme est le suivant :
G possede-t-il un sous-graphe complet d'au moins
k-sommets (ie. un graphe dont tous les sommets sont relies deux a deux
par une arrete) ?
Si le graphe contient un sous-graphe complet complet a k
sommets alors, en toute logique, le nombre d'arretes est : k(k + 1) /
2. On va denommer cette valeur nb pour une question de simplicite dans
le reste du document.
Donc, si nb >= |E|, alors la donnee est impossible a traiter et on la rejette.
Dans le cas contraire, on a k = O(sqrt(|E|)) = O(sqrt(n)) avec n >= |V| + |E| la taille de la donnee.
Il suffit maintenant, grace au non-determinisme du systeme
sur lequel on s'appuie (NRAM), d'obtenir la liste des k-sommets
composant la clique, que l'on garde en memoire.
On doit ensuite verifier que les sommets sont tous relies entre eux deux a deux. L'espace necessaire vaut donc k = O(sqrt(n)) .
Il nous suffit ensuite de calculer le temps de verification des arretes ce qui nous donne O(nb) = O(n)
On a donc bien verifie que le probleme de la clique peut
etre resolu en temps n et en espace sqrt(n) et donc qu'il appartient a
la classe NTISP(n, sqrt(n))
Les
problemes comme les arbres de plan-recouvrement, le sac-a-dos, la
partition, et d'autres encore, appartiennent aussi a la classe NTISP(n,
sqrt(n))
On dispose en entree de :
Le probleme est le suivant :
Peut-on choisir, pour chaque hypercube de la grille, un de ses paves autorises, de telle sorte que deux hypercubes adjacents aient la meme couleur sur leur face commune ?
On se propose de regarder si, pour tout entier d >= 2, le probleme est dans la classe NTISP(n, n^(1 – 1/d))
Considerons le cas d >= 2:
On considere un rectangle de m x n carres, chacun avec un ensemble non-vide de paves. On suppose que n >= m et la taille de la donnee est t >= mn. On ne regarde toujours au pire que deux rangees car on verifie la conformite de la rangee elle-meme mais aussi avec sa rangee d'apres.
Une fois que l'on passe a la rangee d'apres, la seule rangee utile est celle d'apres, celle d'avant n'est plus d'aucune utilite et peut donc etre liberee de la memoire. Chaque rangee est de taille m donc l'espace utilise est toujours le meme :
O(sqrt(t)) (car m <= sqrt (mn) <= sqrt (t)).
De plus, il est facile de constater que le processus dans son ensemble se fait en temps O (mn) = O (t)
Il existe deux types de RAM :
Une RAM est matétiellement constituée :
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 :
