Ｐ≠ＮＰ問題についての質問です。

質問

Ｐ≠ＮＰ問題についての質問です。

この問題の議論されている意味が分かったような？分からんような？、なので質問します。

大方の研究者は、「Ｐ≠ＮＰ」ではないか？、という予想をしているようですが、この問題の結論は、

(1)Ｐ＝ＮＰ
(2)Ｐ≠ＮＰ

のどちらかひとつ、という解釈で間違いありませんか？

また、(1)と証明された場合、「全てのＮＰ問題はＰ問題に属する。」ことを示さねばなりませんよね？現在、ＮＰ問題（例：ナップザック問題、ハミルトン閉路問題・・・）とされている、全てのものが「ＮＰ⊂Ｐ」であることを証明しないと、「Ｐ＝ＮＰ」、であることは証明されたことになりませんよね？（全てについて調べなければいけないのか、それとも、ひとつでいいのか？）

一方で、(2)と証明された場合、「少なくともひとつのＮＰ問題はＰ問題に属さない。」ことを示せば大丈夫ですよね。
即ち、「何かひとつでいいから、ＮＰ問題であるけど、多項式アルゴリズムがない。」という問題を証明すればいいんですね？？（全てについて調べなければいけないのか、それとも、ひとつでいいのか？）

冒頭で書いた「Ｐ≠ＮＰが有力」というのは、「ひとつでいいからＰ問題に属さないＮＰ問題を見つければ良い。（多項式時間帰着可能でない、非決定性チューリングマシンが存在する。）」という裏付けであると考えていいのでしょうか。

ど素人なので勘違いしているかもしれませんが、解説お願いいたします。

回答No.1

rinkun · ベストアンサー

Ｐ＝ＮＰをいうにはＮＰ完全問題のうち一つがＰに属すると証明すれば十分です。
実のところ、ＮＰ完全問題に属する問題のうち一つでもＰに属することが証明できれば、全てのＮＰ問題がＰに属することが証明できます。ＮＰ完全問題はＮＰの中でもっとも難しいことが証明された問題クラスなのです。

逆にＰ≠ＮＰを示すにはＮＰでかつＰでない問題を一つでも見つければ良いのは事実です。
しかし、ある問題がＰに属さないことを示すのは大変です。なぜならＰを示すにはＰクラスのアルゴリズムを一つ見つければ良いですが、Ｐでないことを示すにはどんなＰクラスのアルゴリズムでも解けないという不可能の証明をしなければいけないからです。

お礼

ありがとうございます。

もう一度考えてみます。