longueurs polynomiale connexes de moins de deux codages différents

Question

Je lis par "Computers and Intractability: A guide to the Theory of NP-Completeness" by Michael R. Garey and David S. Johnson, p. 20 et je suis tombé sur ce concept d'une fonction qui est polynomiale liée à des longueurs d'entrée obtenues en utilisant une méthode de codage. Laissez $$ Len: D _ {\ Pi} \ rightarrow \ mathbb Z ^ + $$ une fonction que les cas cartes $ \ in D _ {\ Pi} $ (l'ensemble des instances de problème de décision $ \ Pi $) à des nombres entiers positifs (longueurs). Soit $ x $ la chaîne obtenue à partir de $ I \ dans D _ {\ Pi} $ sous un encodage $ e $. S'il existe des polynômes $ p $ et $ p '$ tel que Len $$ (I) \ le p (| x |) $$ et $$ | x | \ Le p '(Len (I)), $$ On dit que $ Len $ est liée polynomiale aux longueurs d'entrée obtenues par le codage $ e $. Je ne peux pas digérer que; je crois comprendre que deux encodages sont liés polynomiale si la conversion d'un autre nécessite une quantité polynomiale de temps. Quelqu'un peut-il clarifier les choses un peu?

Answer 1

Garey et Johnson font référence au fait que tout système de codage pour une instance I $ $ d'un problème $ \ Pi $ sera seulement en longueur différente (à savoir le nombre de bits) par une quantité polynomiale. Par exemple, envisager deux façons de coder un graphique. Matrice contiguïté, et la liste des contiguïté

Il est impossible d'obtenir un gain de vitesse super-polynomiale en utilisant un codage sur une autre pour divers cas de problèmes. Encore une fois, cette notion repose sur le fait que les codages sont raisonnable . C'est-à-dire, nous ne sommes pas Rembourrage inutilement notre encodage avec des informations « junk ».