パーティションはどのようにして問題になるのですか？擬似多項式実行時間はありますか？

Question

私は、パーティションの問題が疑似多項式ランタイムを持つ方法について混乱しています。疑似ポリ時間とは、アルゴリズムが入力の数値に対して多項式時間wrtで実行されるが、入力のサイズで指数関数的に実行されることを意味する。パーティションの問題では、入力は整数の集合です（サイズnとしましょう）。したがって、入力のサイズはすべてのn個の整数を表すのに必要なビット数です。パーティションアルゴリズムはO（n * M）の時間で実行されます。ここでMは与えられた整数の（絶対値）の合計ですが、このランタイムがビット数で指数関数的であるという接続を作成する方法はわかりません入力から。どんな助けでも大歓迎です。ありがとう！

Answer 1

入力ビット数xを呼び出します。

各入力番号はO（x/n）ビットです。

したがって、各入力番号のサイズはO（2 ^（x/n））になります。

したがって、MはO（n.2 ^（x/n））になります。

したがって、アルゴリズムはO（n^2.2 ^（x/n））であり、xが増加すると指数関数的に増加します。