Réduction plolynomiale.

Posté par mamadimitriou mamadimitriou

salut à tous !!
Voici quelques jours que je me retrouve confronté
à un petit problème en théorie de la complexité.
Dans le livre de Papadimitriou page 160 on donne la
définition d'une réduction:

Une fonction R d'un langage L1 dans un langage L2 est une réduction
s'il existe une machine de Turing  M la calculant en SPACE O(log n )  et telle que
x appartient à L1 si et seulement si R(x) appartient a L2.

La proposition suivant la définition nous indique qu'une réduction  
se calcule en temps polynomiale, la preuve commence ainsi :

La machine M possède au plus, pour chaque entrée x,  un nombre de configurations en O(nc^log(n)) ou n est la longueur de x....
Je ne vois pas vraiment l'argument permettant d'affirmer cela ... Est-ce en rapport avec le fait que
NSPACE (f(n)) est inclus dans TIME(k^(log(n) +f(n) ) ?


MErci !