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