NPC 問題のセットの構築を開始するには、最初の問題があったはずです。そうして初めて、NP の問題が NPC の最初の問題に還元可能であることを示すことによって、集合 NP から集合 NPC に問題を追加することができます。では、NPC に最初に追加された問題は何であり、それが実際に NPC であると誰かがどのように結論付けたのでしょうか。
(注: Google で検索しましたが、答えはありません。ここの誰かの教授がクラスでこのようなことを言っていたことを願っています)
1 に答える
2
それは充足可能性またはSATの問題でした。
履歴： http：
//en.wikipedia.org/wiki/Boolean_satisfiability_problem
于 2012-12-08T02:41:14.627 に答える