古典的な物理問題をNP完全であるスピングラス形式で表すことは自明ではないですか?

80年代後半にSpin-Glassモデルを使用して、次のような他の計算上の問題を定式化するいくつかの取り組みが行われました。タンパク質折り畳みおよびニューラルネットワークを参照してください。

古典物理学の問題をスピングラスに還元することは簡単ではないでしょうか?それは NP完成です問題?

私が言っているのは、スピングラスは少なくとも古典的な物理モデルと同じくらい強力なモデル(computionaly)なので、いつもスピングラスを使って古典的なシステムを再現することができるということです。

これらの2つの論文は非常に引用されているので、私はここで大きなポイントを逃していると思う。

EDIT: If you downvote, please consider to add a
constructive comment.

ベストアンサー

古典的な物理的問題は、NP完全問題の典型である離散集合(整数など)の値ではなく、実数の位置またはパラメータ値を含むことがよくあります。このため、これらの問題はしばしばNP困難ではありますが、NP完全ではありません(または明らかではありません)。例えば、ユークリッドTSP(ユークリッド距離を持つ平面上の整数点)がNP完全であるかどうかは、未解決の問題、平方根の合計を比較する複雑さ実在論の実在理論を参照してください。私たちが知る限り、NPとは異なる複雑さのクラスです。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です