拙訳: 擬多項式時間アルゴリズムとは何か

上記の記事が分かりやすかったので訳してみます。翻訳に問題がある場合はコメントにてご指摘お願いいたします。 質問 擬多項式時間とは何でしょうか。多項式時間とは何が違うのでしょうか。 擬多項式時間アルゴリズムとして、例えば 0-1 ナップザック問題を O(nW) で解くアルゴリズムや、 O(\sqrt{n}) で素数判定を行う試し割り法 などがありますが、 これらはなぜ多項式時間とみなされないのでしょうか。 回答 多項式時間と擬多項式時間の違いを理解するために、まず「多項式時間」とは何を意味するのかをきちんと形式的に把握する必要があります。 直感的には、多項式時間とは、ある k に対して時間計算量が O(n^k) と書けることですね。 例えば 選択ソートは O(n^2) の多項式時間アルゴリズムです。一方、巡回セールスマン問題 をしらみつぶしに解く方法は O(n \cdot n!) かかり、多

[catindog]

“この事実は暗号論的に重要です。もし RSA 暗号を使いたければ、私たちは暗号に使う数が簡単には素因数分解できないことを信じなければなりません。入力のビット長を巨大な数へと（例えば 1024bit など）増やすことによ