巡回セールスマン問題、MAX-SAT、グラフの最小色数の検出など、NP困難であることが知られている多くの最適化問題があります。この種の問題を考えると、私は次の問題の複雑さに興味があります。
NP困難最適化問題と候補解Sが与えられた場合、Sは問題の最適解ですか？
直感的には、より良い解決策を推測してそれを証人として使用することで最適化問題への答えに反論するのは簡単なので、これは共同NP困難であるように思われますが、これをどのように示すかわかりません。実際、私はこの問題の複雑さについて推論する方法を本当に知りません。
この決定問題の複雑さに関する適切な下限を知っている人はいますか？これがco-NPハード、PSPACEハードなどであるかどうかを知ることは本当に興味深いでしょう。
「NP困難最適化問題」という用語は、満足のいく答えを見つけるには少し広すぎるようです。
たとえば、決定問題がNP困難な最適化問題と見なされるのを妨げるものがわかりません。たとえば、ソリューションがfloor（k / N）としてスコアリングされるMAX-CNF-SAT問題を考慮すると、kは満たされた句の数とNは、インスタンス内の句の総数（多項式時間で明らかに計算可能）である場合、この式で1を生成する評価は、式全体を満たす必要があります。したがって、floor（k / N）を最大化していると仮定し、これをFLOOR-CNF-SAT最適化問題と呼びます:)
これは、TAUTOLOGYを上記の最適化問題に減らすことができることを意味します。入力を否定し、任意の解をSとして追加します。ダミー変数を追加して、FLOOR-CNF-SAT問題で初期解が0になるようにすることもできます。否定は時間的に多項式です。
次に、提案された問題のソルバーがSが最適でないと判断した場合、作成された関数に従って1を生成し、式全体を満たす評価が明らかに存在する必要があります。つまり、元の入力を満たさない評価を提供します。トートロジー。
TAUTOLOGYはco-NP-completeであることが簡単に示されるため、（人工的に作成された最適化問題を使用して）わずかに不正行為を行うことにより、「最適」問題をco-NP-completeとして確立しました。
あなた自身の議論によれば、「最適な」決定問題は共同NP困難です。なぜなら、証人として必要なのはより良い解決策だけであるためです。Sをスコアリングし、証人をスコアリングして比較します。
この削減についてはあまり気分が良くありませんが、問題のあるクラスを簡単に改善することはできません。{0、1}だけでなく、任意に高いスコアのインスタンスが必要な場合は、N * floor（k / N）を使用できます。クラスの改善は、Kごとに、スコアがすべて異なる少なくともK個の解を持つインスタンスが存在する場合にのみ、問題をNP困難最適化問題と見なすことです。
私はまだそれを通して自分の道をだますことができると思います：
次のように、N個のダミー変数をTAUTOLOGY入力に追加する削減について考えてみます。
d1 && d2 && d3 ... && dN && (S)
ここで、Sは否定された入力です。初期評価としてd1、...、dN = falseを選択しますが、スコアとして、最初のN句がすべてfalseの場合は2N -1を返す関数を指定し、それ以外の場合は満たされている句の数を返します。このような関数は、すべての句が満たされた場合にのみ2Nを返しますが、少なくともN個の異なる値を簡単に持つことができます。
スコアリング関数に複雑な規則性条件がなければ、これが得られる最善の方法であると思います。ただし、NP困難な最適化問題の定義を、候補解Sが与えられた場合に、次のような問題と見なさない限りです。多項式時間は、Sが最適であるかどうかを検証します。この場合、「最適である」は明らかにPであり、まったく面白くありません。
NP困難な問題は、「少なくともNPで最も困難な問題と同じくらい難しい」です。
NP困難問題の例：停止問題（プログラムAが停止できるかどうか）:)
候補解があるとしましょう：「いいえ、プログラムAは停止できません」。私たちは、あなたがそれを検証することができないことを知っています-それは決定不可能です。
「はい、プログラムAが停止する」かどうかを確認することすらできません。これは、永遠にかかる可能性があるため、決定不可能です。
Sは候補解であるため。Sが他のどのSよりも貪欲であるか最適でないことが証明できるSは他にありません。現在、Sが問題の最も最適なソリューションである必要があります。