Schéma d'approximation en temps entièrement polynomial

Un schéma d'approximation en temps entièrement polynomial (FPTAS, pour ) est un algorithme permettant de trouver des solutions approximatives aux problèmes fonctionnels, en particulier aux problèmes d'optimisation. Un FPTAS prend en entrée une instance du problème et un paramètre ε > 0. Il renvoie en sortie une valeur d'au moins fois la valeur correcte, et au plus fois la valeur correcte. Dans le contexte des problèmes d'optimisation, ce qu'on appelle valeur correcte est la valeur de la solution optimale. Il est souvent sous-entendu qu'un FPTAS doit produire une solution valide (et pas seulement la valeur de la solution). Retourner une valeur et trouver une solution avec cette valeur sont équivalents si l'on suppose que le problème possède une autoréductibilité. Pour un FPTAS, on demande que le temps d'exécution soit polynomial en la taille de l'instance et en 1/ε. Ainsi, un FPTAS est plus contraint qu'un schéma général d'approximation en temps polynomial (PTAS). Le temps d'exécution d'un PTAS général est polynomial dans la taille du problème pour chaque ε spécifique, mais peut être exponentiel en 1/ε. Le terme FPTAS peut également être utilisé pour désigner la classe de problèmes qui ont un FPTAS. FPTAS est un sous-ensemble de PTAS qui, sauf si P=NP est un sous-ensemble strict. Tous les problèmes dans FPTAS sont traitables à paramètres fixes par rapport à la paramétrisation standard. Tout problème d'optimisation fortement NP-difficile (autrement dit qui reste NP-difficile si on considère les nombres de l'instance écrit en unaire) avec une fonction objectif polynômialement bornée ne peut pas avoir de FPTAS à moins que P = NP Cependant, la réciproque n'est pas vrai : par exemple, si P n'est pas égal à NP, le sac à dos avec deux contraintes n'est pas fortement NP-difficile, mais n'a pas de FPTAS même lorsque l'objectif optimal est polynômialement borné. Woeginger a présenté une méthode générale pour transformer une certaine classe de programmes dynamiques en FPTAS.