計算論の問題

以下の文章には誤解を招く表現があります. 具体的に記しなさい.

問題の難しさのクラス P と NP

問題を計算機で解く場合には、まず具体的な問題 (instance) を何らかの形で入力しなければなりません。その入力に必要なビット数を N とします。このとき、ある多項式 P(x) に対して、計算量が O(P(N)) となるような、この問題を解くアルゴリズムが存在するとき、この問題はクラス P に属するといいます。
もう少し難しい問題のクラスとして、NP があります。ある問題とその答えが与えられた時に、その答えが正しいということを確認するのに必要な計算量が多項式オーダーとなります。この問題のクラスが NP です。NP の N は Nondeterministic（非決定性）の N なのですが、それについての説明はここでは省略します。
あきらかに、ハミルトン閉路問題と巡回セールスマン問題は NP のクラスに属します。答えが与えられれば、それがちゃんと問題の解になっていることを確かめるのは簡単であるからです。また、クラス P の問題はすべてNP にも含まれています。
なお、NP 問題では与えられた問題に指定された解がない場合についての規定はありません。与えられた問題に指定された解がないという判定を行う問題は、これらの問題の双対問題と呼ばれます。NP 問題の双対問題がつくる問題のクラスは co-NP と呼ばれています。
例えば
1,3,5,7,13,14,17,18,23,29
という数字があったとしますよね。これらの数字を組み合わせて（使わない数字があってもよい），『足し算するとちょうど 50 になるような組合せはあるでしょうか？』，『あるとするとそのような組合せは何パターンありますか？』という問題です。
この問題は数字がたかだか10個しかありませんから，しらみつぶしに調べればいずれ答えがあるかどうか，何パターンあるかということは分かるでしょう。しかし，一般的にこの問題はこれといった決定的な解法がなく，総当たりで調べるしか方法がありません。だから，数字が100個，1000個と多くなると途方もない時間がかかってしまいます。
昔，高校の頃『解の公式』を習いましたよね？

の解は

というものでした。このように一般的な解法があるものはあらかじめ計算にどれくらいの時間がかかるのか見積もることが出来ます。これを「多項式時間(Ploymonial-time)で解ける」といいます。
これに対して「素因数分解」や「ナップサック問題」のような問題は決定的な解法が知られておらず，考えられるすべての場合をしらみつぶしに調べなければなりません。このような問題を「多項式時間で解けない(Nondeterministic Polynomial-time)」といいます。
でも，「素因数分解」や「ナップサック問題」は我々がうまい計算の方法を知らないだけで，ひょっとするとうまい方法があるのかも知れません。
そこで P 問題（Polynomial つまり多項式時間で解ける問題）と NP 問題（Nondeterministic Polynomial つまり多項式時間で解けない問題）については

1. P≠NP （世の中には一般的な解法がある問題と，総当たりでしらみつぶしに調べるより他に手がない問題と二通りある）
2. P＝NP （あんたの頭が悪いだけで，一生懸命考えればどんな問題でも一般的な解法があるはず）

のいずれなのだろうという疑問が生じています。たぶん，数学者に限らず頭が良い人々がよってたかって考えても「素因数分解」や「ナップサック問題」のうまい解法を見つけていないので P≠NP なのであろうとは予測されているのですが，まだ証明した人はいません。

ハミルトン閉路問題

与えられたグラフの、同じ辺を通ることなくすべての頂点を通る閉路を求めよ。

巡回セールスマン問題

N 個の都市があり、各都市間の道のりが与えられているとき、すべての都市をめぐる合計の道のりが K 以下となる巡り方を求めよ。

正解.

1. 一瞬 subset sum がco-NPの例に読めてしまう.
2. Subset sumの解の個数を求める問題は#Pじゃないかしら. #P-completeかどうかは知らんが.
3. 後半の説明が不正確.