Bonjour à tous
Avec ce post, mon but n'est pas de réfuter le calcul de la complexité en temps d'une réduction polynomiale, mais bien de comprendre quels sont les conditions qui définissent le calcul de la complexité en temps du problème CNF-SAT en général et où se situe mon incompréhension.
Voici mon problème :
Passionné d'informatique, je m'intéresse à comprendre le problème "P = NP ?", ce qui peut se réduire entre-autres à prouver ou réprouver qu'on peut résoudre le problème SAT en temps polynomial sur une machine déterministe.
Si je comprends bien le problème, le calcul de la complexité en temps de la résolution de SAT doit être faite considérant le pire des cas et en se définissant uniquement sur le nombre de variables () de la formule.
Hors, si l'on considère la réduction polynomiale, qui est définie comme résoluble en temps polynomial comme son nom l'indique, sa complexité est calculée sur le nombre de variables () ET sur le nombre de clauses/éléments () du problème d'entrée considéré.
Cependant, si l'on considère par exemple la réduction de SAT vers 3-SAT, et que l'on définit en fonction de , alors on se retrouve vite dans le pire des cas avec .
 Cliquez pour afficher

Redéfinir le calcul de la complexité d'une telle réduction polynomiale uniquement sur reviens alors à dire que la réduction polynomiale s'effectue en temps exponentiel...

N'es-ce donc pas contradictoire de définir la complexité de la réduction polynomiale sur et alors que l'on ne peut définir celle de CNF-SAT que sur ?
Ou es-ce que le calcul de la complexité en temps de la résolution du problème SAT peut se définir à la fois sur le nombre de variable et sur le nombre de clauses présentes dans la formule ?

Une réduction polynomiale étant de toute évidence exécutable en temps polynomial, je dois certainement mal comprendre certaines notions du calcul de la complexité, pourriez-vous m'indiquer quels sont les erreurs de mon raisonnement ?

Merci d'avoir pris le temps de considérer mes questions et merci d'avance pour vos réponses