2つの異なるエンコーディングの下で​​多項式に関連する長さ

Question

私は読んでいます "Computers and Intractability: A guide to the Theory of NP-Completeness" by Michael R. Garey and David S. Johnson, p. 20 そして、私は、いくつかのエンコードスキームを使用して得られた入力長に多項式に関連するこの関数の概念に出会いました。 $$ len：d _ { pi} rightArrow mathbb z^+$$とします。 （長さ）。 $ x $を、$ i in d _ { pi} $から取得した文字列とし、$ e $をエンコードします。多項式$ p $と$ p '$が存在する場合、$$ len（i） le p（| x |）$$および$$ | x | le p '（len（i））、$$ $ len $は、エンコード$ e $によって得られた入力長に多項式に関連していると言います。私はそれを消化することはできません。私の理解では、互いに変換するには多項式時間が必要な場合、2つのエンコーディングが多項式に関連しているということです。誰かが少し物事を明確にすることができますか？

Answer 1

GareyとJohnsonは、問題$ Pi $のインスタンス$ i $のエンコードスキームの長さ（つまり、ビット数）が多項式量によってのみ異なるという事実に言及しています。たとえば、グラフをエンコードする2つの考えられる方法を検討してください：隣接マトリックスと隣接リスト。

問題のさまざまなインスタンスに対して、あるエンコードを別のエンコードで使用して、スーパーポリノームスピードアップを取得することはできません。繰り返しますが、この概念はエンコーディングが 適正. 。つまり、私たちはエンコードを「ジャンク」情報で不必要にパディングしているわけではありません。