計算論の問題 - 186 @ hatenablog

以下の文章には誤解を招く表現があります. 具体的に記しなさい. 問題の難しさのクラス P と NP 問題を計算機で解く場合には、まず具体的な問題 (instance) を何らかの形で入力しなければなりません。その入力に必要なビット数を N とします。このとき、ある多項式 P(x) に対して、計算量が O(P(N)) となるような、この問題を解くアルゴリズムが存在するとき、この問題はクラス P に属するといいます。 もう少し難しい問題のクラスとして、NP があります。ある問題とその答えが与えられた時に、その答えが正しいということを確認するのに必要な計算量が多項式オーダーとなります。この問題のクラスが NP です。NP の N は Nondeterministic（非決定性）の N なのですが、それについての説明はここでは省略します。 あきらかに、ハミルトン閉路問題と巡回セールスマン問題は N

[nobody]

寄席ブックマーク