Polynomial verwandte Längen unter zwei verschiedenen Kodierungen

Question

Ich lese durch "Computers and Intractability: A guide to the Theory of NP-Completeness" by Michael R. Garey and David S. Johnson, p. 20 Und ich bin auf dieses Konzept einer Funktion gestoßen, die polynomial mit Eingangslängen zusammenhängt, die unter Verwendung eines Codierungsschemas erhalten wurden. Sei $$ len: d _ { pi} rightarrow mathbb z^+$$ eine Funktion, die Instanzen $ in d _ { pi} $ montiert (Längen). Sei $ x $ die Zeichenfolge, die von $ i in d _ { pi} $ unter einigen Codierung $ e $ erhalten wurde. Wenn es Polynome gibt $ p $ und $ p '$ so, dass $$ len (i) le p (| x |) $$ und $$ | x | le p '(len (i)), $$ Wir sagen, dass $ len $ polynomial mit den Eingabelängen zusammenhängt, die durch die Codierung $ e $ erhalten wurden. Ich kann das nicht verdauen; Mein Verständnis ist, dass zwei Kodierungen polynomial verwandt sind, wenn die Konvertierung voneinander eine Polynomzeit erfordert. Kann jemand die Dinge ein bisschen klären?

Answer 1

Garey und Johnson beziehen sich auf die Tatsache, dass jedes Codierungsschema für ein Beispiel $ i $ eines Problems $ pi $ nur in der Länge (dh Anzahl der Bits) nach einem Polynombetrag unterscheidet. Betrachten Sie beispielsweise zwei mögliche Möglichkeiten zur Codierung eines Diagramms: Adjazenzmatrix und Adjazenzliste.

Es ist nicht möglich, eine superpolynomiale Beschleunigung zu erhalten, indem eine Codierung über einen anderen für verschiedene Probleme von Problemen verwendet wird. Auch dieser Begriff beruht auf der Tatsache, dass Codierungen sind angemessen. Das heißt, wir haben unsere Codierung nicht unnötig mit einigen "Junk" -Informationen auf unsere Codierung einbezogen.