疑似多項式vs。多項式の複雑さ
1. 序章
このチュートリアルでは、疑似多項式と多項式の複雑さの違いについて説明します。
2. 複雑
時間計算量分析の目標は、入力のサイズが大きくなるにつれてアルゴリズムが実行するステップ数の漸近限界を導出することです。たとえば、時間計算量は、入力のサイズが無期限に大きくなる場合を意味します。 、アルゴリズムはほとんどのステップで実行されます。ここで、は正の定数です。 ステップを時間単位に変換すると、期間もの2次関数であることがわかります。
ただし、入力サイズの問題が発生します。 入力のサイズの適切な尺度は何ですか？
2.1. サイズはビット数です
アルゴリズム分析では、入力サイズはそれを書き留めるのに必要なビット数です。 たとえば、入力が整数の配列である場合、分析の実際のサイズは、マシンレベルで整数を格納する方法に応じて、またはになります。 同様に、行列のサイズはまたはです。
2.2. 要素を数え、正しい結果を得ることができます
一般に、次のルールが適用されます。
(1)
すべての要素が同じタイプである場合（ほとんどの場合）、次のようになります。
(2)
単一要素あたりのビット数が入力要素の総数に対して一定である限り、分析では無視できます。 なんで？ 乗法定数は複雑さを変えないからです。
したがって、実際に行う-element配列のサイズとして使用するのが安全です。 同じことが、行列などの他の入力タイプにも当てはまります。
3. 疑似多項式の複雑さ
ビット数ではなく入力の大きさで複雑さを表現するとどうなるでしょうか。
の代わりに、を使用するとします。ここで、アルゴリズムへの入力を構成します。 分析の技術的な詳細は変更されません。 MasterやAkra-Bazziの定理などの同じツールが適用されます。 ただし、入力サイズの標準定義を使用した場合とは異なる結果が得られる場合があります。 そのため、複雑さが疑似多項式であるアルゴリズムと言います。例を見てみましょう。
3.1. 疑似多項式素数性問題
数値がprimeであるかどうかを確認する簡単な方法の擬似コードは次のとおりです。
3.2. 分析
アルゴリズムはほとんどの反復で実行されます。 物事を単純化するために、私たちのマシンには低レベルの計算方法があると仮定します。 次に、アルゴリズムの時間計算量はであると結論付けることができます。
ただし、入力番号をメモリに格納するためのビットが必要です。 なので、サイズの複雑さはです。 それで、アルゴリズムは線形ですか、それとも指数関数ですか？
コンピューターはデータをバイナリ文字列（0と1で構成される）として格納するため、後者の結果は、計算の実行方法とより一致します。一方、単一のメモリセル内の数値。複雑さを数値で表す方が適切です。 したがって、それはすべて、入力のより自然でより合理的な表現に帰着します。
4. なぜ疑似多項式の複雑さを気にするのですか？
とともにゆっくりと成長するため、数値アルゴリズムの指数関数的な性質は、入力数が十分に大きい場合にのみ実現されます。 したがって、その値を制限できる場合、またはほとんどの場合それが適度に低くなることが確実である場合は、時間の複雑さについてあまり心配する必要はありません。
しかし、その逆も成り立ちます。数値アルゴリズムを遅くしたい場合、疑似多項式の複雑さは、非常に大きな数を使用するように指示します。これは、たとえば暗号化の場合です。 たとえば、多項式時間で数値を効率的に因数分解できれば、暗号化アルゴリズムとしてRSAに依存することはできません。 したがって、RSA暗号化のユーザーはそのような主要な要素を選択し、その製品の要素分解は攻撃者の現在の計算能力を超えています。
5. 結論
