私は、このアルゴリズムのためarticle on wikipdiaで探しています、と私は2つの一見矛盾の文を参照してください。和解クワイン・マクラスキーアルゴリズム
は、「それはまた、ブール関数の最小のフォームをことを確認するために、決定論的な方法を提供しますそれが解決の問題はNP困難であることから 『
を使用する限定された範囲を持っている」
と
』に達してきました
思考？
P.S.ハイライトされたコードにこのアルゴリズムを適用して条件付きロジックを減らすことができるVisual Studioプラグインはありますか？
アルゴリズムは指数関数的な時間を要します。すべてのNP完全問題は、指数関数的な時間で解くことができます。おそらく、言及された問題は、NP困難であることに加えてNP完全である。あなたは完全NP困難の定義を理解していないので、
不一致はおそらくです： http://en.wikipedia.org/wiki/NP-hard
矛盾するものは何もこれらのステートメントではありません。
コンピュータサイエンスのは、決定論的アルゴリズムは、非公式の用語では、予想通りに動作するアルゴリズムです：
あなたは「決定論」は、この文脈では何を意味するのかについて混乱するかもしれません。特定の入力が与えられると、常に同じ出力が生成され、基底のマシンは常に同じ状態のシーケンスを通過します。この意味でwikipedia
から
は、ほとんどすべての広く使われているCSアルゴリズムは決定されています。
私はあなたがすでに何を意味するのか「NP-ハード」:)
非決定論的である*アルゴリズム*と*非決定性多項式*複雑性クラスを混同しないでください知っていると確信しています。 2つの非常に異なるもの。 – marcog