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 !