NP - アンドロイドはしあわせか

よくある間違いをここに書くことがけっこうあるなぁ。「よくある間違い」カテゴリでも作ろうかな。 クラスNPについて。 とりあえず前置きだが P : (deterministic) Polynomial NP : Nondeterministic Polynomial である。 クラス P に属する問題とは、決定問題(decision problem: 答えがyes/noの問題)のうち、決定性計算（deterministic computation, 説明は後述）によって多項式時間(Polynomial time)で解が得られる問題のことである。 多項式時間とは、その問題の解を得るまでの計算時間が、問題サイズ(problem size)の多項式関数である、ということ。 ここでの（計算複雑性理論での）時間というのは、実際の物理的な時間をどうこう言うのではなく、問題サイズに相対的な計算ステップ数（

[ysibata]

sicp