PLS (複雑さ)

計算複雑性理論において、多項式局所探索 ( PLS ) は、最適化問題に対する局所最適解を見つける難しさをモデル化する複雑性クラスです。PLS に含まれる問題の主な特徴は、解のコストが多項式時間で計算でき、解の近傍が多項式時間で検索できることです。したがって、解が局所最適解であるかどうかを多項式時間で検証できます。さらに、問題と問題の解決に使用されるアルゴリズムによっては、大域最適解ではなく局所最適解を見つける方が速い場合があります。

局所最適解を探す場合、対処すべき興味深い問題が 2 つあります。1 つ目は局所最適解を見つける方法、2 つ目は局所最適解を見つけるのにどれくらい時間がかかるかです。多くの局所探索アルゴリズムでは、局所最適解を多項式時間で見つけられるかどうかはわかっていません。^[1]そのため、局所最適解を見つけるのにどれくらい時間がかかるかという疑問に答えるために、ジョンソン、パパディミトリウ、およびヤンナカキス^{[2] は} 、論文「局所探索はどれくらい簡単か?」で複雑性クラス PLS を導入しました。これには、局所最適解が多項式時間で検証できる局所探索問題が含まれています。

次の特性が満たされる場合、ローカル検索問題は PLS に該当します。

• すべてのソリューションのサイズは、インスタンスのサイズに対して多項式的に制限されます。${\displaystyle I}$
• 問題インスタンスの何らかの解決策を多項式時間で見つけることは可能です。
• 各ソリューションのコストは多項式時間で計算できます。
• 各解のすべての近傍を多項式時間で見つけることが可能です。

これらの特性により、各ソリューションに対して最適な近傍ソリューションを見つけることが可能になり、また、そのようなより優れた近傍ソリューションがない場合は、それが局所最適であると述べることができます。 ${\displaystyle s}$${\displaystyle s}$

Max-2Sat問題の次の例を考えてみましょう。目的は、満たされる節の合計を最大化する割り当てを見つけることです。 ${\displaystyle I}$${\displaystyle (x_{1}\vee x_{2})\wedge (\neg x_{1}\vee x_{3})\wedge (\neg x_{2}\vee x_{3})}$

そのインスタンスの解は、 すべての に値 0 または 1 を割り当てるビット文字列です。この場合、解は 3 ビットで構成されます。たとえば、 は をに値 0 を割り当てることを表します。解の集合は、 、およびのすべての可能な割り当ての集合です。 ${\displaystyle s}$${\displaystyle x_{i}}$${\displaystyle s=000}$${\displaystyle x_{1}}$${\displaystyle x_{3}}$${\displaystyle F_{L}(I)}$${\displaystyle x_{1}}$${\displaystyle x_{2}}$${\displaystyle x_{3}}$

各ソリューションのコストは満たされる節の数です。したがって、2 番目と 3 番目の節は満たされます。 ${\displaystyle c_{L}(I,s=000)=2}$

解のFlip-近傍は、ビット文字列の 1 ビットを反転することによって到達されるため、 の近傍は次のコストで 得られます。${\displaystyle s}$${\displaystyle s}$${\displaystyle s}$${\displaystyle N(I,000)=\{100,010,001\}}$

${\displaystyle c_{L}(I,100)=2}$

${\displaystyle c_{L}(I,010)=2}$

${\displaystyle c_{L}(I,001)=2}$

最大コストのソリューションを探している場合、よりもコストのよい近傍は存在しません。はグローバル最適値 (たとえば、すべての節を満たし、 であるソリューション)ではありませんが、 の近傍にはコストのよい近傍がないため、 はローカル最適値です。 ${\displaystyle s}$${\displaystyle s}$${\displaystyle s'=111}$${\displaystyle c_{L}(I,s')=3}$${\displaystyle s}$

直感的には、この問題はPLS にあると主張できます。その理由は次のとおりです。

• たとえば、すべてのビットを 0 に設定することにより、多項式時間でインスタンスの解を見つけることができます。
• インスタンス全体を一度実行し、満たされる節を数えることで、ソリューションのコストを多項式時間で計算できます。
• 正確に 1 ビットだけ異なる解の集合を取ることによって、多項式時間で解のすべての近傍を見つけることが可能です。${\displaystyle s}$

満たされた節の数を単純に数える場合、可能なコストの数は多項式なので、問題は多項式時間で解決できます。ただし、各節に正の整数の重みを割り当てて（満たされた節の重みの合計を局所的に最大化するようにすると）、問題は PLS 完全になります（以下）。

局所探索問題には、有限のアルファベット上の文字列を使用してエンコードされたインスタンスの集合があります。各インスタンスには、有限の解集合が存在します。をモデル化する関係とします。次の場合、 関係はPLS ^{[2] [3] [4]}に属します。${\displaystyle L}$${\displaystyle D_{L}}$ ${\displaystyle \Sigma }$${\displaystyle I}$${\displaystyle F_{L}(I)}$${\displaystyle R}$${\displaystyle L}$${\displaystyle R\subseteq D_{L}\times F_{L}(I):=\{(I,s)\mid I\in D_{L},s\in F_{L}(I)\}}$

• あらゆる解の大きさは、${\displaystyle s\in F_{L}(I)}$${\displaystyle I}$
• 問題インスタンスとソリューションは多項式時間で検証可能である${\displaystyle I\in D_{L}}$${\displaystyle s\in F_{L}(I)}$
• 各インスタンスに対して何らかの解を返す多項式時間計算可能な関数がある${\displaystyle A:D_{L}\rightarrow F_{L}(I)}$${\displaystyle I\in D_{L}}$${\displaystyle s\in F_{L}(I)}$
• 多項式時間で計算可能な関数^[5]があり、インスタンスの各解に対してコストを返す。${\displaystyle B:D_{L}\times F_{L}(I)\rightarrow \mathbb {R} ^{+}}$ ${\displaystyle s\in F_{L}(I)}$${\displaystyle I\in D_{L}}$${\displaystyle c_{L}(I,s)}$
• インスタンスとソリューションのペアの近傍集合を返す多項式時間計算可能な関数がある。${\displaystyle N:D_{L}\times F_{L}(I)\rightarrow Powerset(F_{L}(I))}$
• 解よりもコストの低い近傍解を返す多項式時間計算可能な関数、または局所的に最適である状態を返す関数が存在する。${\displaystyle C:D_{L}\times F_{L}(I)\rightarrow N(I,s)\cup \{OPT\}}$${\displaystyle s'}$${\displaystyle s}$${\displaystyle s}$
• あらゆる例 に対して、はの局所最適解であるペアを正確に含んでいます。${\displaystyle I\in D_{L}}$${\displaystyle R}$${\displaystyle (I,s)}$${\displaystyle s}$${\displaystyle I}$

インスタンスは暗黙のグラフ（遷移グラフ^[6]とも呼ばれる）の構造を持ち、頂点は2つの解が有向弧で接続されている場合の解である。 ${\displaystyle D_{L}}$ ${\displaystyle s,s'\in F_{L}(I)}$${\displaystyle s'\in N(I,s)}$

局所最適解とは、近傍にコストのよりよい解が存在しない解である。暗黙のグラフでは、局所最適解はシンクである。すべての局所最適解がグローバル最適解、つまり可能な限り最良のコストを持つ解である近傍は、正確な近傍と呼ばれる。^{[6] [1]}${\displaystyle s}$

PLSクラスは、多項式時間でSink-of- DAG ^[7]問題（Local-Opt ^[8]とも呼ばれる）に還元できるすべての問題を含むクラスです。2つの整数とと、およびとなる2つのブール回路が与えられたとき、およびまたはとなる頂点を見つけます。 ${\displaystyle n}$${\displaystyle m}$ ${\displaystyle S:\{0,1\}^{n}\rightarrow \{0,1\}^{n}}$${\displaystyle S(0^{n})\neq 0^{n}}$${\displaystyle V:\{0,1\}^{n}\rightarrow \{0,1,..,2^{m}-1\}}$${\displaystyle x\in \{0,1\}^{n}}$${\displaystyle S(x)\neq x}$${\displaystyle S(S(x))=S(x)}$${\displaystyle V(S(x))\leq V(x)}$

ブール変数 (またはビット文字列) をソリューションとして使用する問題の近傍構造の例:

• 反転^[2] - 解の近傍は、任意の1つの入力ビットを反転（反転）することで実現できます。したがって、1つの解とそのすべての近傍のハミング距離は1です。${\displaystyle s=x_{1},...,x_{n}}$${\displaystyle x_{i}}$${\displaystyle s}$${\displaystyle r\in N(I,s)}$${\displaystyle H(s,r)=1}$
• Kernighan-Lin ^{[2] [6]} -貪欲な反転のシーケンスによってから が得られる場合、解は の近傍です。貪欲な反転のシーケンスでは、ビットは 2 回反転されません。つまり、 から始めて、最善のコスト、またはコストの損失が最小となる のFlip近傍が、Kernighan-Lin 構造の s の近傍として選ばれます。 の最良 (または最悪でない) 近傍などと同様に、が のすべてのビットが否定される解になるまで続きます。一度反転したビットを元に戻すことはできないことに注意してください。${\displaystyle r}$${\displaystyle s}$${\displaystyle r}$${\displaystyle s}$${\displaystyle s}$${\displaystyle s_{1}}$${\displaystyle s}$${\displaystyle s_{1}}$${\displaystyle s_{i}}$${\displaystyle s}$
• k-フリップ^[9] - 解は、との間のハミング距離が最大で であるとき、つまりであるとき、解の近傍である。${\displaystyle r}$${\displaystyle s}$ ${\displaystyle H}$${\displaystyle s}$${\displaystyle r}$${\displaystyle k}$${\displaystyle H(s,r)\leq k}$

グラフ上の問題の近傍構造の例:

• スワップ^[10] - グラフ内のノードのパーティションは、 1つのノードを別のノードと交換することでから取得できる場合、パーティションの隣接ノードです。${\displaystyle (P_{2},P_{3})}$${\displaystyle (P_{0},P_{1})}$${\displaystyle (P_{2},P_{3})}$${\displaystyle (P_{0},P_{1})}$${\displaystyle p_{0}\in P_{0}}$${\displaystyle p_{1}\in P_{1}}$
• Kernighan-Lin ^{[1] [2]} - パーティションは、内のノードを 内のノードと貪欲に交換することによって取得できる場合、の隣接ノードです。つまり、2 つのノードと が交換され、パーティションの重みが最大になるか、または重みが最小になります。ノードを 2 回交換することはできないことに注意してください。このルールは、グラフ パーティションの Kernighan-Lin ヒューリスティックに基づいています。${\displaystyle (P_{2},P_{3})}$${\displaystyle (P_{0},P_{1})}$${\displaystyle (P_{2},P_{3})}$${\displaystyle P_{0}}$${\displaystyle P_{1}}$${\displaystyle p_{0}\in P_{0}}$${\displaystyle p_{1}\in P_{1}}$${\displaystyle ((P_{0}\setminus p_{0})\cup p1,(P_{1}\setminus p_{1})\cup p_{0})}$
• Fiduccia-Matheyses ^{[1] [11]} - この近傍はKernighan-Lin近傍構造に似ており、貪欲なスワップシーケンスですが、各スワップは2段階で行われます。最初に、コストのゲインが最も高い、またはコストの損失が最も少ないノードが にスワップされ、次に、コストが最も高い、またはコストの損失が最も少ないノードが にスワップされて、パーティションのバランスが再び取られます。実験により、Fiduccia-Mattheysesは標準アルゴリズムの各反復で実行時間が短くなることが示されていますが、劣った局所最適値が見つかることもあります。${\displaystyle p_{0}\in P_{0}}$${\displaystyle P_{1}}$${\displaystyle p_{1}\in P_{1}}$${\displaystyle P_{0}}$
• FM-スワップ^[1] - この近傍構造は、Fiduccia-Mattheyses近傍構造に基づいています。各ソリューションには、Fiduccia-Mattheysesの最初のスワップ後に取得されたパーティションである1つの近傍のみがあります。${\displaystyle s=(P_{0},P_{1})}$

次の計算問題を考えてみましょう。PLS 問題 のいくつかのインスタンスが与えられた場合、すべての に対してとなるような局所最適解を見つけます${\displaystyle I}$${\displaystyle L}$${\displaystyle s\in F_{L}(I)}$${\displaystyle c_{L}(I,s')\geq c_{L}(I,s)}$${\displaystyle s'\in N(I,s)}$。

あらゆる局所探索問題は、以下の反復改善アルゴリズムを使用して解決できます。^[2]

1. 初期ソリューションを見つけるために使用する${\displaystyle A_{L}}$${\displaystyle s}$
2. アルゴリズムを使用してより良い解決策を見つけます。そのような解決策が存在する場合は、を に置き換えて手順2を繰り返します。そうでない場合は、 を返します。${\displaystyle C_{L}}$${\displaystyle s'\in N(I,s)}$${\displaystyle s}$${\displaystyle s'}$${\displaystyle s}$

残念ながら、たとえ問題が多項式時間で正確に解ける場合でも、局所最適解を見つけるには通常、指数関数的な数の改善ステップが必要です。^{[2]常に標準アルゴリズムを使用する必要はなく、特定の問題に対してはより高速な別のアルゴリズムが存在する可能性があります。たとえば、}線形計画法に使用される局所探索アルゴリズムは、シンプレックスアルゴリズムです。 ${\displaystyle L}$

標準アルゴリズムの実行時間は、ソリューションの異なるコストの数の擬似多項式です。 ^[12]

標準的なアルゴリズムに必要なスペースは多項式だけです。定義によって多項式で制限される現在の解を保存するだけで済みます。^[1]${\displaystyle s}$

ある問題を別の問題に還元すると、2 番目の問題が少なくとも最初の問題と同じくらい難しいことが示されます。特に、PLS 還元は、PLS 完全問題を PLS 完全であることが証明される問題に還元することで、PLS 内にあるローカル検索問題も PLS 完全であることを証明するのに使用されます。

局所探索問題は、2つの多項式時間関数と次のような 場合、 PLS還元可能^[2]な局所探索問題である。${\displaystyle L_{1}}$${\displaystyle L_{2}}$${\displaystyle f:D_{1}\rightarrow D_{2}}$${\displaystyle g:D_{1}\times F_{2}(f(I_{1}))\rightarrow F_{1}(I_{1})}$

• が のインスタンスである場合、 はのインスタンスである。${\displaystyle I_{1}}$${\displaystyle L_{1}}$${\displaystyle f(I_{1})}$${\displaystyle L_{2}}$
• が の解である場合、 はの解である。${\displaystyle s_{2}}$${\displaystyle f(I_{1})}$${\displaystyle L_{2}}$${\displaystyle g(I_{1},s_{2})}$${\displaystyle I_{1}}$${\displaystyle L_{1}}$
• が のインスタンスに対して局所最適値である場合、 は のインスタンスに対して局所最適値である必要があります。${\displaystyle s_{2}}$${\displaystyle f(I_{1})}$${\displaystyle L_{2}}$${\displaystyle g(I_{1},s_{2})}$${\displaystyle I_{1}}$${\displaystyle L_{1}}$

の局所最適値を の局所最適値にマッピングするだけで十分であり、他のすべての解を、例えば によって返される標準解にマッピングするだけで十分である。^[6]${\displaystyle f(I_{1})}$${\displaystyle I_{1}}$${\displaystyle A_{1}}$

PLS還元は推移的である。^[2]

問題のインスタンスの遷移グラフ^[6] は有向グラフです。ノードは有限の解集合のすべての要素を表し、エッジは 1 つの解から厳密にコストのよい近傍の解を指します。したがって、これは非巡回グラフです。シンク (出力エッジのないノード) は局所最適です。頂点の高さは、最も近いシンクまでの最短経路の長さです。遷移グラフの高さは、すべての頂点の高さの中で最大であるため、ノードから最も近いシンクまでの最大最短経路の高さになります。 ${\displaystyle T_{I}}$${\displaystyle I}$${\displaystyle L}$${\displaystyle F_{L}(I)}$${\displaystyle v}$${\displaystyle v}$

局所探索問題から局所探索問題へのPLS縮約は、任意のインスタンスに対して、インスタンスの解のサブセットを選択でき、次の特性が満たされる場合、 タイトPLS縮約^[10]である 。${\displaystyle (f,g)}$${\displaystyle L_{1}}$${\displaystyle L_{2}}$${\displaystyle I_{1}}$${\displaystyle L_{1}}$${\displaystyle R}$${\displaystyle I_{2}=f(I_{1})}$${\displaystyle L_{2}}$

• ${\displaystyle R}$他の解の中でも、すべての局所最適解を含む${\displaystyle I_{2}}$
• の解のすべてに対して、の解は多項式時間で構築できるため、${\displaystyle p}$${\displaystyle I_{1}}$${\displaystyle q\in R}$${\displaystyle I_{2}=f(I_{1})}$${\displaystyle g(I_{1},q)=p}$
• の遷移グラフに から への直接パスと が含まれるが、すべての内部パス頂点が の外側にある場合、対応する解および に対してが成り立つか、からへの辺が含まれる。${\displaystyle T_{f(I_{1})}}$${\displaystyle f(I_{1})}$${\displaystyle q}$${\displaystyle q_{0}}$${\displaystyle q,q_{0}\in R}$${\displaystyle R}$${\displaystyle p=g(I_{1},q)}$${\displaystyle p_{0}=g(I_{1},q_{0})}$${\displaystyle p=p_{0}}$${\displaystyle T_{I_{1}}}$${\displaystyle p}$${\displaystyle p_{0}}$

PLSはPとNPの機能バージョンの間に位置します：FP ⊆ PLS ⊆ FNP。^[2]

PLSはTFNP ^[13]のサブクラスでもあり、解の存在が保証され、多項式時間で認識できる計算問題を記述します。PLSの問題では、グラフ全体の最小コストの頂点が有効な解であるため、解の存在が保証され、解の有効性は近傍を計算し、それぞれのコストを比較することで確認できます。

PLS問題がNP困難である場合、NP = co-NPであることも証明されています。^[2]

局所探索問題はPLS完全である^[2]。 ${\displaystyle L}$

• ${\displaystyle L}$PLSにあります
• PLSにおけるすべての問題はPLS縮約できる。${\displaystyle L}$

フリップ近傍構造における回路問題の最適化バージョンは、最初のPLS完全問題であることが示されている。^[2]

これは、PLS 完全である既知の問題の不完全なリストです。ここでの問題は重み付けされたバージョンです。たとえば、Max-2SAT は通常は重み付けされていないバージョンを指しますが、Max-2SAT/Flip は重み付けされています。

表記: 問題 / 近傍構造

• Min/Max-circuit/Flipは最初のPLS完全問題であることが証明されている。 ^[2]
• Sink-of -DAGは定義上完全です。
• Positive-not-all-equal-max-3Sat/Flipは、 Min/Max-circuit/FlipからPositive-not-all-equal-max-3Sat/FlipへのタイトなPLS還元によってPLS完全であることが証明されています。Positive-not-all-equal-max-3Sat/FlipはMax-Cut/Flipからも還元できることに留意してください。^[10]
• Positive-not-all-equal-max-3Sat/Kernighan-Linは、 Min/Max-circuit/FlipからPositive-not-all-equal-max-3Sat/Kernighan-Linへの緊密なPLS還元によってPLS完全であることが証明されています。^[1]
• Max-2Sat /Flipは、 Max-Cut/FlipからMax-2Sat/Flipへの緊密なPLS縮約によりPLS完全であることが証明されている。 ^{[1] [10]}
• Min-4Sat-B /Flipは、Min-circuit/FlipからMin-4Sat-B/Flipへの緊密なPLS還元によってPLS完全であることが証明されている。 ^[9]
• Max-4Sat-B/Flip（またはCNF-SAT）は、Max-circuit/FlipからMax-4Sat-B/FlipへのPLS縮約によりPLS完全であることが証明されている。^[14]
• Max-4Sat-(B=3)/Flipは、 Max-circuit/FlipからMax-4Sat-(B=3)/FlipへのPLS還元によりPLS完全であることが証明されている。^[15]
• Max-Uniform-Graph-Partitioning /Swapは、Max-Cut/FlipからMax-Uniform-Graph-partitioning/Swapへの緊密なPLS還元によってPLS完全であることが証明されている。 ^[10]
• Max-Uniform-Graph-Partitioning /Fiduccia-Matheysesは証明なしにPLS完全であると述べられている。 ^[1]
• Max-Uniform-Graph-Partitioning /FM-Swapは、 Max-Cut/FlipからMax-Uniform-Graph-partitioning/FM-Swapへの緊密なPLS削減によりPLS完全であることが証明されている。 ^[10]
• Max-Uniform-Graph-Partitioning /Kernighan-Lin は、 Min/Max-circuit/Flip から Max-Uniform-Graph-Partitioning/Kernighan-Lin への PLS 簡約によって PLS 完全であることが証明されています。 ^[2] Positive-not-all-equal-max-3Sat/Kernighan-Lin から Max-Uniform-Graph-Partitioning/Kernighan-Lin へのタイトな PLS 簡約もあります。 ^[1]
• Max-Cut /Flipは、Positive-not-all-equal-max-3Sat/FlipからMax-Cut/Flipへの緊密なPLS還元によってPLS完全であることが証明されている。 ^{[1] [10]}
• Max-Cut /Kernighan-Linは証明なしにPLS完全であると主張されている。 ^[6]
• Min-Independent-Dominating-Set-B/k-Flipは、 Min-4Sat-B ′ /FlipからMin-Independent-Dominating-Set-B/k-Flipへの緊密なPLS還元によってPLS完全であることが証明されている。^[9]
• 重み付き独立集合/変更は証明なしにPLS完全であると主張されている。 ^{[2] [10] [6]}
• 最大加重サブグラフ特性P/Changeは、特性P = 「辺を持たない」場合、加重独立集合/Changeと等しくなるため、PLS完全である。また、加重独立集合/Changeから最大加重サブグラフ特性P/Changeへの緊密なPLS還元により、一般的な遺伝的、非自明な特性Pに対してPLS完全であることが証明されている。^[16]
• Set-Cover /k-changeは、 (3, 2, r)-Max-Constraint-Assignment/ChangeからSet-Cover/k-changeへのタイトなPLS還元により、k ≥ 2の各kに対してPLS完全であることが証明されている。 ^[17]
• Metric-TSP /k-Changeは、Max-4Sat-B/FlipからMetric-TSP/k-ChangeへのPLS還元によりPLS完全であることが証明されている。 ^[15]
• Metric-TSP /Lin-Kernighanは、Max-2Sat/FlipからMetric-TSP/Lin-Kernighanへの緊密なPLS還元によりPLS完全であることが証明されている。 ^[18]
• ローカルマルチプロセッサスケジューリング/k-changeは、重み付き3次元マッチング/(p, q)-スワップからローカルマルチプロセッサスケジューリング/(2p+q)-changeへのタイトなPLS削減によってPLS完全であることが証明されています（ここで、(2p + q) ≥ 8）。 ^[5]
• Selfish-Multi-Processor-Scheduling/k-change-with-property-tは、Weighted-3Dimensional-Matching/(p, q)-Swapから(2p+q)-Selfish-Multi-Processor-Scheduling/k-change-with-property-tへのタイトなPLS縮約によってPLS完全であることが証明されている（ここで、(2p + q) ≥ 8）。^[5]
• 一般混雑ゲーム/Changeにおける純粋なナッシュ均衡を見つけることは、Positive-not-all-equal-max-3Sat/Flipから一般混雑ゲーム/Changeへの緊密なPLS還元によってPLS完全であることが証明されている。^[19]
• 対称的な一般混雑ゲーム/変化における純粋なナッシュ均衡を見つけることは、非対称的な一般混雑ゲーム/変化から対称的な一般混雑ゲーム/変化への緊密なPLS還元を通じてPLS完全であることが証明されている。^[19]
• 非対称な有向ネットワーク輻輳ゲーム/変更における純粋なナッシュ均衡の発見は、Positive-not-all-equal-max-3Sat/Flipから有向ネットワーク輻輳ゲーム/変更への緊密な還元[19 ^{]と、2-Threshold-Games/変更から有向ネットワーク輻輳ゲーム/変更への緊密なPLS還元[20]}によってPLS完全であることが証明されている。
• 非対称無向ネットワーク輻輳ゲーム/変化における純粋なナッシュ均衡を見つけることは、2閾値ゲーム/変化から非対称無向ネットワーク輻輳ゲーム/変化への厳密なPLS還元によってPLS完全であることが証明されている。^[20]
• 対称距離制限ネットワーク輻輳ゲームにおける純粋なナッシュ均衡の発見は、2閾値ゲームから対称距離制限ネットワーク輻輳ゲームへの厳密なPLS還元によってPLS完全であることが証明されている。^[21]
• 2閾値ゲーム/チェンジにおける純粋なナッシュ均衡を見つけることは、マックスカット/フリップから2閾値ゲーム/チェンジへの厳密な還元を通じてPLS完全であることが証明されている。^[20]
• 多項式制限コストを持つ市場分割ゲーム/変化における純粋なナッシュ均衡を見つけることは、2閾値ゲーム/変化から市場分割ゲーム/変化への厳密なPLS還元によってPLS完全であることが証明されている。^[20]
• オーバーレイネットワーク設計/変更における純粋なナッシュ均衡を見つけることは、2閾値ゲーム/変更からオーバーレイネットワーク設計/変更への還元によってPLS完全であることが証明されている。非対称な有向ネットワーク輻輳ゲーム/変更の証明と同様に、還元は厳密である。^[20]
• Min-0-1-整数計画法/k-Flipは、Min-4Sat-B ′ /FlipからMin-0-1-整数計画法/k-Flipへの緊密なPLS縮約によりPLS完全であることが証明されている。 ^[9]
• Max-0-1-整数計画法/k-Flipは、Max-0-1-整数計画法/k-FlipへのPLS還元によりPLS完全であると主張されているが、証明は省略されている。 ^[9]
• (p, q, r)-最大制約割り当て
  • (3, 2, 3)-最大制約割り当て3部構成/変更は、 Circuit/Flipから(3, 2, 3)-最大制約割り当て3部構成/変更への緊密なPLS還元によってPLS完全であることが証明されている。^[22]
  • (2, 3, 6)-最大制約割り当て2部/変更は、 Circuit/Flipから(2, 3, 6)-最大制約割り当て2部/変更への緊密なPLS還元によってPLS完全であることが証明されている。^[22]
  • (6, 2, 2)-Max-Constraint-Assignment/Changeは、 Circuit/Flipから(6, 2, 2)-Max-Constraint-Assignment/Changeへの緊密な還元を通じてPLS完全であることが証明されている。^[22]
  • (4, 3, 3)-Max-Constraint-Assignment/ChangeはMax-4Sat-(B=3)/Flipに等しく、Max-circuit/FlipからのPLS縮約によりPLS完全であることが証明されている。^[15]縮約を拡張してタイトネスを得ることができると主張されている。^[22]
• Nearest-Colorful-Polytope/Changeは、 Max-2Sat/FlipからNearest-Colorful-Polytope/ChangeへのPLS還元によりPLS完全であることが証明されている。^[3]
• ホップフィールドネットワークにおける安定構成/フリップは、閾値が0で重みが負の場合、最大カット/フリップから安定構成/フリップへの緊密なPLS削減によりPLS完全であることが証明されている。^{[1] [10] [18]}
• 重み付き3次元マッチング/(p, q)-スワップは、(2, 3, r)-最大制約割り当て-2部/変更から重み付き3次元マッチング/(p, q)-スワップへの緊密なPLS縮約により、p ≥ 9およびq ≥ 15に対してPLS完全であることが証明されています。 ^[5]
• Real-Local-Opt問題（ λ-リプシッツ連続目的関数と近傍関数のɛ局所最適値を求める問題）はPLS完全である。^[8]${\displaystyle V:[0,1]^{3}\rightarrow [0,1]}$${\displaystyle S:[0,1]^{3}\rightarrow [0,1]^{3}}$
• NKモデル/ポイント突然変異によって指定された生物学的適応度ランドスケープにおいてK≥2の局所適応度ピークを見つけることは、Max-2SAT/FlipからのタイトなPLS削減によってPLS完全であることが証明されました。^[23]

Fearnley、Goldberg、Hollender、Savani ^[24]は、CLSと呼ばれる複雑性クラスがPPADとPLSの積に等しいことを証明した。

• 均衡、固定点、複雑性クラス：概観^[25]

• ヤンナカキス、ミハリス(2009)、「均衡、不動点、複雑性クラス」、コンピュータサイエンスレビュー、3 (2): 71–85、CiteSeerX  10.1.1.371.5034、doi :10.1016/j.cosrev.2009.03.004。