長いですが、NP完全について質問です。 アルゴリズムの本に 「図のどれがP、NP、NP完全(NPCと呼びます)のクラスについての私たちの知識と矛盾しているか？ "=Which of the diagrams do not contradict the current state of our knowledge about the complexity classes P, NP, and NPC (NP-complete problems)"」 という質問があってヒントに 「これらのうちの二つのみが現在の私たちの知識と矛盾している "=Just two of them do not contradict the current state of our knowledge about the complexity classes."」とあります。 「私たちの知識」とはその本に載っている 「もしP≠NPなら、PでもNP完全でもないNP問題があるはずだ "=It is known that if P≠NP, there must exist NP problems that neither are in P nor are NP-complete."」 っぽいです。
