---

Psuedopolynomial(疑多項式)について

多項式時間でとける問題(selection sortなど)は、入力の多項式時間O(n^k)で示される
例えば入力がbitで示されるとき、1bit増えると計算量は２倍である。このときO(2^kn)のような形で示され、入力が増えるごとに爆発的に計算量が増える(そしてこれは多項式時間でない)
多項式時間では表現が適切でなく、入力に含まれる数量の多項式で表せるときに疑多項式と呼ぶ
暗号理論の複素数が含まれるのは擬多項式だからである

参考

• 拙訳: 擬多項式時間アルゴリズムとは何か
• NとかNPとか困難とか完全とか（２）