20/05/2007
La classe NTISP
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).
- La classe NTISP (n, sqrt (n))
Nous disposons en entree :
- d'un graphe G = (V, E)
- d'un entier positif k <= |V|
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))
- Autres problemes appartenant a cette classe
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))
- La classe NTISP (n, n^(1 - 1/d))
On dispose en entree de :
- d entiers m1, m2, ..., md
- une grille m1 x m2 x ... x md de dimension d, avec pour chaque hypercube de la grille un ensemble de paves autorises, chacun ayant ses faces colores
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)
