PLS (složitost) - PLS (complexity)

v teorie výpočetní složitosti, Polynomiální místní vyhledávání (PLS) je třída složitosti který modeluje obtížnost nalezení a místně optimální řešení pro optimalizační problém. Hlavní charakteristikou problémů, které spočívají v PLS, je, že lze vypočítat náklady na řešení polynomiální čas a okolí řešení lze prohledávat v polynomiálním čase. Proto je možné ověřit, zda řešení je či není lokálním optimem v polynomiálním čase. Dále, v závislosti na problému a algoritmu, který se používá k řešení problému, může být rychlejší najít lokální optimum místo globálního optima .

Popis

Při hledání místního optima je třeba se zabývat dvěma zajímavými problémy: Zaprvé, jak najít lokální optimum, a zadruhé, jak dlouho trvá najít lokální optimum. U mnoha místních vyhledávacích algoritmů není známo, zda mohou najít lokální optimum v polynomiálním čase nebo ne.^[1] Abychom odpověděli na otázku, jak dlouho trvá najít místní optimum, Johnson, Papadimitriou a Yannakakis ^[2] představili třídu složitosti PLS ve svém příspěvku „Jak snadné je místní vyhledávání“. Obsahuje problémy s místním vyhledáváním, u nichž lze ověřit lokální optimálnost v polynomiálním čase.

Problém s místním vyhledávání je v PLS, pokud jsou splněny následující vlastnosti:

• Velikost každého řešení je polynomiálně ohraničena velikostí instance ${displaystyle I}$.
• Je možné najít nějaké řešení problémové instance v polynomiálním čase.
• Je možné vypočítat náklady na každé řešení v polynomiálním čase.
• Je možné najít všechny sousedy každého řešení v polynomiálním čase.

S těmito vlastnostmi je možné najít pro každé řešení ${displaystyle s}$ nejlepší sousední řešení, nebo pokud takové lepší sousední řešení neexistuje, uveďte to ${displaystyle s}$ je lokální optimum.

Příklad

Zvažte následující příklad ${displaystyle I}$ z Max-2Sat Problém: ${displaystyle (x_ {1} vee x_ ​​{2}) klín (např. x_ {1} vee x_ ​​{3}) klín (např. x_ {2} vee x_ ​​{3})}$. Cílem je najít zadání, které maximalizuje součet splněných klauzulí.

A řešení ${displaystyle s}$ pro tuto instanci je bitový řetězec, který přiřadí každý ${displaystyle x_ {i}}$ hodnota 0 nebo 1. V tomto případě se řešení skládá například ze 3 bitů ${displaystyle s = 000}$, což znamená přiřazení ${displaystyle x_ {1}}$ na ${displaystyle x_ {3}}$ s hodnotou 0. Sada řešení ${displaystyle F_ {L} (I)}$ je sada všech možných přiřazení ${displaystyle x_ {1}}$, ${displaystyle x_ {2}}$ a ${displaystyle x_ {3}}$.

The náklady každého řešení je počet splněných klauzulí, takže ${displaystyle c_ {L} (I, s = 000) = 2}$ protože druhá a třetí věta jsou splněny.

Flip-soused řešení ${displaystyle s}$ je dosaženo převrácením jednoho bitu bitového řetězce ${displaystyle s}$, takže sousedé ${displaystyle s}$ jsou ${displaystyle N (I, 000) = {100 010 001}}$ s následujícími náklady:

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

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

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

Neexistují žádní sousedé s lepšími náklady než ${displaystyle s}$, pokud hledáme řešení s maximálními náklady. Přestože ${displaystyle s}$ není globálním optimem (což by bylo například řešení ${displaystyle s '= 111}$ který splňuje všechny doložky a má ${displaystyle c_ {L} (I, s ') = 3}$), ${displaystyle s}$ je místní optimum, protože žádný z jeho sousedů nemá lepší náklady.

Intuitivně lze tvrdit, že tento problém leží v PLS, protože:

• Je možné najít řešení instance v polynomiálním čase, například nastavením všech bitů na 0.
• Je možné vypočítat náklady na řešení v polynomiálním čase tak, že jednou projdete celou instanci a spočítáte klauzule, které jsou splněny.
• Je možné najít všechny sousedy řešení v polynomiálním čase pomocí sady řešení, která se liší od ${displaystyle s}$ přesně v jednom bitu.

Formální definice

Problém s místním vyhledáváním ${displaystyle L}$ má sadu ${displaystyle D_ {L}}$ případů, které jsou kódovány pomocí struny přes konečnou abeceda ${displaystyle Sigma}$. Pro každou instanci ${displaystyle I}$ existuje sada konečných řešení ${displaystyle F_ {L} (I)}$. Nechat ${displaystyle R}$ být vztah, který modely ${displaystyle L}$. Vztah ${displaystyle Rsubseteq D_ {L} imes F_ {L} (I): = {(I, s) mid Iin D_ {L}, sin F_ {L} (I)}}$ je v PLS ^{[2] [3][4]} li:

• Velikost každého řešení ${displaystyle sin F_ {L} (I)}$ je polynom ohraničený velikostí ${displaystyle I}$
• Problémové instance ${displaystyle Iin D_ {L}}$ a řešení ${displaystyle sin F_ {L} (I)}$ jsou polynomiální časově ověřitelné
• Existuje polynomiální časově vypočítatelná funkce ${displaystyle A: D_ {L} ightarrow F_ {L} (I)}$ který se vrací pro každou instanci ${displaystyle Iin D_ {L}}$ nějaké řešení ${displaystyle sin F_ {L} (I)}$
• Existuje polynomiální časově vypočítatelná funkce ${displaystyle B: D_ {L} imes F_ {L} (I) ightarrow mathbb {R} ^ {+}}$ ^[5] který se vrací pro každé řešení ${displaystyle sin F_ {L} (I)}$ instance ${displaystyle Iin D_ {L}}$ náklady ${displaystyle c_ {L} (I, s)}$
• Existuje polynomiální časově vypočítatelná funkce ${displaystyle N: D_ {L} imes F_ {L} (I) ightarrow Powerset (F_ {L} (I))}$ která vrací sadu sousedů pro pár instance-řešení
• Existuje polynomiální časově vypočítatelná funkce ${displaystyle C: D_ {L} imes F_ {L} (I) ightarrow N (I, s) cup {OPT}}$ který vrací sousední řešení ${displaystyle s '}$ s lepšími náklady než řešení ${displaystyle s}$nebo to uvádí ${displaystyle s}$ je lokálně optimální
• Pro každou instanci ${displaystyle Iin D_ {L}}$, ${displaystyle R}$ přesně obsahuje páry ${displaystyle (I, s)}$ kde ${displaystyle s}$ je lokální optimální řešení ${displaystyle I}$

Instance ${displaystyle D_ {L}}$ má strukturu implicitní graf (také zvaný Přechodový graf ^[6]), přičemž vrcholy jsou řešeními se dvěma řešeními ${displaystyle s, s'in F_ {L} (I)}$ spojeno směrovaným obloukem, pokud ${displaystyle s'in N (I, s)}$.

A místní optimum je řešení ${displaystyle s}$, který nemá žádného souseda s lepšími náklady. V implicitním grafu je lokálním optimem jímka. Sousedství, kde je každé místní optimum globální optimum, což je řešení s nejlepšími možnými náklady, se nazývá přesné sousedství.^[6][1]

Příklad sousedských struktur

Příklad struktur sousedství pro problémy s booleovskými proměnnými (nebo bitovými řetězci) jako řešení:

• Flip^[2] - Sousedství řešení ${displaystyle s = x_ {1}, ..., x_ {n}}$ lze dosáhnout vyvrácením (převrácením) jednoho libovolného vstupního bitu ${displaystyle x_ {i}}$. Takže jedno řešení ${displaystyle s}$ a všichni jeho sousedé ${displaystyle rin N (I, s)}$ mít Hammingova vzdálenost jeden: ${displaystyle H (s, r) = 1}$.
• Kernighan-Lin^[2][6] - Řešení ${displaystyle r}$ je soused řešení ${displaystyle s}$ -li ${displaystyle r}$ lze získat z ${displaystyle s}$ posloupností chamtivých převrácení, kdy se žádný bit nepřevrátí dvakrát. To znamená, počínaje ${displaystyle s}$, Flip-soused ${displaystyle s_ {1}}$ z ${displaystyle s}$ s nejlepší cenou nebo s nejnižší ztrátou nákladů, je vybrán jako soused s ve struktuře Kernighan-Lin. Stejně jako nejlepší (nebo nejméně nejhorší) soused ${displaystyle s_ {1}}$ , a tak dále, dokud ${displaystyle s_ {i}}$ je řešení, kde každý kousek ${displaystyle s}$ je negován. Všimněte si, že není povoleno převrátit trochu zpět, pokud již bylo jednou převráceno.
• k-Flip^[7] - Řešení ${displaystyle r}$ je soused řešení ${displaystyle s}$ pokud Hammingova vzdálenost ${displaystyle H}$ mezi ${displaystyle s}$ a ${displaystyle r}$ je nanejvýš ${displaystyle k}$, tak ${displaystyle H (s, r) leq k}$.

Příklad sousedských struktur pro problémy v grafech:

• Zaměnit^[8] - Oddíl ${displaystyle (P_ {2}, P_ {3})}$ uzlů v grafu je sousedem oddílu ${displaystyle (P_ {0}, P_ {1})}$ -li ${displaystyle (P_ {2}, P_ {3})}$ lze získat z ${displaystyle (P_ {0}, P_ {1})}$ zaměněním jednoho uzlu ${displaystyle p_ {0} v P_ {0}}$ s uzlem ${displaystyle p_ {1} v P_ {1}}$.
• Kernighan-Lin^[1][2] - Oddíl ${displaystyle (P_ {2}, P_ {3})}$ je soused ${displaystyle (P_ {0}, P_ {1})}$ -li ${displaystyle (P_ {2}, P_ {3})}$ lze získat chamtivou sekvencí swapů z uzlů v ${displaystyle P_ {0}}$ s uzly v ${displaystyle P_ {1}}$. To znamená dva uzly ${displaystyle p_ {0} v P_ {0}}$ a ${displaystyle p_ {1} v P_ {1}}$ jsou zaměněny, kde je oddíl ${displaystyle ((P_ {0} setminus p_ {0}) pohár p1, (P_ {1} setminus p_ {1}) pohár p_ {0})}$ získává nejvyšší možnou váhu nebo ztrácí nejméně možnou váhu. Všimněte si, že žádný uzel nesmí být zaměněn dvakrát.
• Fiduccia-Matheyses ^[1][9] - Toto sousedství je podobné struktuře sousedství Kernighan-Lin, jedná se o chamtivou sekvenci swapů, až na to, že každý swap probíhá ve dvou krocích. Nejprve ${displaystyle p_ {0} v P_ {0}}$ s největším ziskem z nákladů nebo s nejnižší ztrátou nákladů, je vyměněn za ${displaystyle P_ {1}}$, pak uzel ${displaystyle p_ {1} v P_ {1}}$ s největšími náklady nebo s nejmenší ztrátou nákladů ${displaystyle P_ {0}}$ znovu vyvážit oddíly. Pokusy ukázaly, že Fiduccia-Mattheyses má v každé iteraci standardního algoritmu kratší dobu běhu, i když někdy najde nižší lokální optimum.
• Výměna FM^[1] - Tato struktura sousedství je založena na struktuře sousedství Fiduccia-Mattheyses. Každé řešení ${displaystyle s = (P_ {0}, P_ {1})}$ má pouze jednoho souseda, oddíl získaný po první výměně Fiduccia-Mattheyses.

Standardní algoritmus

Zvažte následující výpočetní problém:Vzhledem k nějaké instanci ${displaystyle I}$ problému s PLS ${displaystyle L}$, najít lokálně optimální řešení ${displaystyle sin F_ {L} (I)}$ takhle ${displaystyle c_ {L} (I, s ') geq c_ {L} (I, s)}$ pro všechny ${displaystyle s'in N (I, s)}$.

Každý problém s místním vyhledávání lze vyřešit pomocí následujícího algoritmu iterativního vylepšení:^[2]

1. Použití ${displaystyle A_ {L}}$ najít počáteční řešení ${displaystyle s}$
2. Použijte algoritmus ${displaystyle C_ {L}}$ najít lepší řešení ${displaystyle s'in N (I, s)}$. Pokud takové řešení existuje, vyměňte jej ${displaystyle s}$ podle ${displaystyle s '}$ a opakujte krok 2, jinak se vraťte ${displaystyle s}$

Bohužel obvykle trvá exponenciální počet kroků ke zlepšení, aby se našlo místní optimum, i když je problém ${displaystyle L}$ lze vyřešit přesně v polynomiálním čase.^[2] Není nutné vždy používat standardní algoritmus, pro určitý problém může existovat jiný, rychlejší algoritmus. Například použitý místní vyhledávací algoritmus Lineární programování je Simplexní algoritmus.

Doba běhu standardního algoritmu je pseudo-polynom v počtu různých nákladů na řešení.^[10]

Prostor, který standardní algoritmus potřebuje, je pouze polynomiální. Je potřeba pouze uložit aktuální řešení ${displaystyle s}$, což je polynom ohraničený definicí.^[1]

Snížení

A Snížení jednoho problému k druhému lze použít k prokázání, že druhý problém je přinejmenším stejně obtížný jako ten první. Zejména redukce PLS se používá k prokázání toho, že problém místního vyhledávání, který spočívá v PLS, je také PLS-úplný, redukcí problému PLS-úplného na ten, u kterého se prokáže, že je PLS-úplný.

PLS-redukce

Problém s místním vyhledáváním ${displaystyle L_ {1}}$ je PLS-redukovatelný^[2] k problému s místním vyhledáváním ${displaystyle L_ {2}}$ pokud existují dvě polynomiální časové funkce ${displaystyle f: D_ {1} ightarrow D_ {2}}$ a ${displaystyle g: D_ {1} imes F_ {2} (f (I_ {1})) ightarrow F_ {1} (I_ {1})}$ takové, že:

• -li ${displaystyle I_ {1}}$ je instancí ${displaystyle L_ {1}}$ , pak ${displaystyle f (I_ {1})}$ je instancí ${displaystyle L_ {2}}$
• -li ${displaystyle s_ {2}}$ je řešení pro ${displaystyle f (I_ {1})}$ z ${displaystyle L_ {2}}$ , pak ${displaystyle g (I_ {1}, s_ {2})}$ je řešení pro ${displaystyle I_ {1}}$ z ${displaystyle L_ {1}}$
• -li ${displaystyle s_ {2}}$ je například lokální optimum ${displaystyle f (I_ {1})}$ z ${displaystyle L_ {2}}$ , pak ${displaystyle g (I_ {1}, s_ {2})}$ musí být například lokálním optimem ${displaystyle I_ {1}}$ z ${displaystyle L_ {1}}$

Postačuje zmapovat pouze místní optima ${displaystyle f (I_ {1})}$ na místní optima ${displaystyle I_ {1}}$a mapovat všechna ostatní řešení, například na standardní řešení vrácené ${displaystyle A_ {1}}$.^[6]

PLS-redukce jsou tranzitivní.^[2]

Pevná redukce PLS

Definice Přechodový graf

Přechodový graf^[6] ${displaystyle T_ {I}}$ instance ${displaystyle I}$ problému ${displaystyle L}$ je směrovaný graf. Uzly představují všechny prvky konečné sady řešení ${displaystyle F_ {L} (I)}$ a hrany směřují od jednoho řešení k sousedovi s přísně lepšími náklady. Jedná se tedy o acyklický graf. Dřez, který je uzlem bez odchozích hran, je lokální optimum. Výška vrcholu ${displaystyle v}$ je délka nejkratší cesty od ${displaystyle v}$ výška přechodového grafu je největší z výšek všech vrcholů, takže je to výška největší nejkratší možné cesty od uzlu k jeho nejbližšímu jímce.

Definice Těsná redukce PLS

Snížení PLS ${displaystyle (f, g)}$ z problému s místním vyhledáváním ${displaystyle L_ {1}}$ k problému s místním vyhledáváním ${displaystyle L_ {2}}$ jetěsná redukce PLS^[8] pokud pro jakoukoli instanci ${displaystyle I_ {1}}$ z ${displaystyle L_ {1}}$podmnožina ${displaystyle R}$ řešení instance ${displaystyle I_ {2} = f (I_ {1})}$ z ${displaystyle L_ {2}}$ lze zvolit, aby byly splněny následující vlastnosti:

• ${displaystyle R}$ obsahuje mimo jiné všechna místní optima ${displaystyle I_ {2}}$
• Pro každé řešení ${displaystyle p}$ z ${displaystyle I_ {1}}$ , řešení ${displaystyle qin R}$ z ${displaystyle I_ {2} = f (I_ {1})}$ lze sestrojit v polynomiálním čase, takže ${displaystyle g (I_ {1}, q) = p}$
• Pokud je přechodový graf ${displaystyle T_ {f (I_ {1})}}$ z ${displaystyle f (I_ {1})}$ obsahuje přímou cestu z ${displaystyle q}$ na ${displaystyle q_ {0}}$, a ${displaystyle q, q_ {0} v R}$, ale všechny vnitřní vrcholy cesty jsou venku ${displaystyle R}$, pak pro odpovídající řešení ${displaystyle p = g (I_ {1}, q)}$ a ${displaystyle p_ {0} = g (I_ {1}, q_ {0})}$ drží buď ${displaystyle p = p_ {0}}$ nebo ${displaystyle T_ {I_ {1}}}$ obsahuje hranu z ${displaystyle p}$ na ${displaystyle p_ {0}}$

Vztah k dalším třídám složitosti

PLS leží mezi funkčními verzemi P a NP: FP ⊆ PLS ⊆ FNP.^[2]

PLS je také podtřídou TFNP,^[11] který popisuje výpočetní problémy, ve kterých je zaručeno, že řešení existuje a které lze rozpoznat v polynomiálním čase. U problému v PLS je zaručeno, že řešení existuje, protože vrchol s minimálními náklady celého grafu je platným řešením a platnost řešení lze zkontrolovat výpočtem jeho sousedů a porovnáním nákladů každého z nich.

Je také prokázáno, že pokud je problém PLS NP-tvrdé, pak NP = co-NP.^[2]

PLS - úplnost

Definice

Problém s místním vyhledáváním ${displaystyle L}$ je PLS kompletní,^[2] -li

• ${displaystyle L}$ je v PLS
• každý problém v PLS lze snížit na PLS ${displaystyle L}$

Optimalizační verze obvod problém pod Flip Ukázalo se, že struktura sousedství je prvním problémem s PLS.^[2]

Seznam úplných problémů s PLS

Toto je neúplný seznam některých známých problémů, které jsou PLS úplné.

Přehled problémů s PLS a jejich vzájemné redukce. Syntax: Struktura optimalizace - problém / sousedství. Tečkovaná šipka: Redukce PLS z problému ${displaystyle L}$ k problému ${displaystyle Q: Lleftarrow Q}$. Černá šipka: Pevná redukce PLS.^[4]

Notace: Struktura problému / sousedství

• Min./max.obvod / Flip se ukázal jako první problém s PLS.^[2]
• Positive-not-all-equal-max-3Sat / Flip bylo prokázáno, že je PLS-úplný díky těsné redukci PLS z Min / Max-obvodu / Flip na Positive-not-all-equal-max-3Sat / Flip. Všimněte si, že Positive-not-all-equal-max-3Sat / Flip lze také snížit z Max-Cut / Flip.^[8]
• Positive-not-all-equal-max-3Sat / Kernighan-Lin bylo prokázáno, že je PLS-kompletní díky těsné redukci PLS z Min / Max-obvodu / Flip na Positive-not-all-equal-max-3Sat / Kernighan-Lin.^[1]
• Max-2Sat / Flip bylo prokázáno, že je PLS-úplný díky těsné redukci PLS z Max-Cut / Flip na Max-2Sat / Flip.^[1][8]
• Min-4Sat-B / Flip bylo prokázáno, že je PLS-úplné díky těsné redukci PLS z Min-circuit / Flip na Min-4Sat-B / Flip.^[7]
• Max-4Sat-B / Flip(nebo CNF-SAT) bylo prokázáno, že je PLS-úplný prostřednictvím redukce PLS z Max-circuit / Flip na Max-4Sat-B / Flip.^[12]
• Max-4Sat- (B = 3) / převrácení bylo prokázáno, že je PLS-úplné prostřednictvím redukce PLS z Max-circuit / Flip na Max-4Sat- (B = 3) / Flip.^[13]
• Max-Uniform-Graph-Partitioning / Zaměnit bylo prokázáno, že je PLS-úplné díky těsné redukci PLS z Max-Cut / Flip na Max-Uniform-Graph-partitioning / Swap.^[8]
• Max-Uniform-Graph-Partitioning / Fiduccia-Matheyses je uvedeno, že je PLS-kompletní bez důkazu.^[1]
• Max-Uniform-Graph-Partitioning / Výměna FM bylo prokázáno, že je PLS-úplný díky těsné redukci PLS z Max-Cut / Flip na Max-Uniform-Graph-partitioning / FM-Swap.^[8]
• Max-Uniform-Graph-Partitioning / Kernighan-Lin bylo prokázáno, že je PLS-úplné prostřednictvím redukce PLS z Min / Max-obvodu / Flip na Max-Uniform-Graph-Partitioning / Kernighan-Lin.^[2] K dispozici je také přísná redukce PLS z Positive-not-all-equal-max-3Sat / Kernighan-Lin na Max-Uniform-Graph-Partitioning / Kernighan-Lin.^[1]
• Max. Řez / Flip bylo prokázáno, že je PLS-úplný díky těsné redukci PLS z Positive-not-all-equal-max-3Sat / Flip na Max-Cut / Flip.^[1][8]
• Max. Řez / Kernighan-Lin se tvrdí, že je kompletní bez PLS.^[6]
• Min-Independent-Dominating-Set-B / k-Flip bylo prokázáno, že je PLS-úplný díky těsné redukci PLS z Min-4Sat-B ’/ Flip na Min-Independent-Dominating-Set-B / k-Flip.^[7]
• Vážená nezávislá sada /Změna se tvrdí, že je kompletní bez PLS.^[2][8][6]
• Maximum-Weighted-Subgraph-with-property-P / Change je PLS-úplné, pokud vlastnost P = „nemá žádné hrany“, protože se potom rovná váženému nezávislému nastavení / změně. Rovněž se prokázalo, že je PLS úplný pro obecnou dědičnou, netriviální vlastnost P prostřednictvím těsné redukce PLS z váženého nezávislého souboru / změny na maximální vážený subgraf s vlastností P / změny.^[14]
• Set-Cover / k-změna bylo prokázáno, že je PLS-kompletní pro každé k ≥ 2 prostřednictvím těsné redukce PLS z (3, 2, r) -Max-Constraint-Assignment / Change to Set-Cover / k-change.^[15]
• Metrické TSP / k-změna bylo prokázáno, že je PLS-úplné prostřednictvím redukce PLS z Max-4Sat-B / Flip na Metric-TSP / k-Change.^[13]
• Metrické TSP / Lin-Kernighan bylo prokázáno, že je PLS-úplný díky těsné redukci PLS z Max-2Sat / Flip na Metric-TSP / Lin-Kernighan.^[16]
• Místní plánování více procesorů / k-změna bylo prokázáno, že je PLS-kompletní díky těsné redukci PLS z Weighted-3Dimensional-Matching / (p, q) -Swap na Local-Multi-Processor-scheduling / (2p + q) -change, kde (2p + q ) ≥ 8.^[5]
• Sobecké plánování více procesorů / k-změna-s-vlastností-t bylo prokázáno, že je PLS-kompletní prostřednictvím těsné redukce PLS z Weighted-3Dimensional Matching / (p, q) -Swap to (2p + q) -Selfish-Multi-Processor-Scheduling / k-change-with-property -t, kde (2p + q) ≥ 8.^[5]
• Nalezení čistá Nashova rovnováha v Obecná hra s přetížením /Změna bylo prokázáno, že PLS-Complete prostřednictvím těsné redukce PLS z Positive-not-all-equal-max-3Sat / Flip na General-Congestion-Game / Change.^[17]
• Nalezení čistá Nashova rovnováha v Symetrická hra s obecným přetížením / změna bylo prokázáno, že je PLS-úplný díky těsné redukci PLS z asymetrické hry General-Congestion-Game / Change na symetrickou hru General-Congestion-Game / Change.^[17]
• Hledání čistého čistá Nashova rovnováha v Asymetrické hry s přetížením v síti / změna bylo prokázáno, že je PLS kompletní díky přísnému snížení z Positive-not-all-equal-max-3Sat / Flip na Directed-Network-Congestion-Games / Change ^[17] a také prostřednictvím přísné redukce PLS z 2-Threshold-Games / Change to Directed-Network-Congestion-Games / Change.^[18]
• Hledání čistého čistá Nashova rovnováha v Asymetrické hry s nepřetíženým síťovým přetížením / změna bylo prokázáno, že je PLS-úplné díky těsné redukci PLS z 2-Threshold-Games / Change to Asymetric Undirected-Network-Congestion-Games / Change.^[18]
• Hledání čistého čistá Nashova rovnováha v 2-Threshold-Game / Change bylo prokázáno, že je PLS kompletní díky přísnému snížení z Max-Cut / Flip na 2-Threshold-Game / Change.^[18]
• Hledání a čistá Nashova rovnováha v Hra o sdílení trhu / změna s polynomiálně ohraničenými náklady bylo prokázáno, že jsou PLS-úplné díky těsnému snížení PLS z 2-Threshold-Games / Change to Market-Sharing-Game / Change.^[18]
• Hledání a čistá Nashova rovnováha v Overlay-Network-Design / Change bylo prokázáno, že je PLS kompletní díky redukci z 2-Threshold-Games / Change to Overlay-Network-Design / Change. Analogicky k důkazu o asymetrické hře / změně s přetížením v síti / změně je redukce přísná.^[18]
• Programování min. 0-1 celých čísel / k-Flip bylo prokázáno, že je PLS-úplné díky těsné redukci PLS z Min-4Sat-B ’/ Flip na Min-0-1-Integer Programming / k-Flip.^[7]
• Max-0-1 celočíselné programování / k-Flip je prohlašováno, že je PLS úplné kvůli redukci PLS na Max-0-1-Integer Programming / k-Flip, ale důkaz je vynechán.^[7]
• (p, q, r) -Max-Constraint-Assignment
  • (3, 2, 3) -Max-Constraint-Assignment-3-partite / Change bylo prokázáno, že je PLS-kompletní díky těsné redukci PLS z Circuit / Flip na (3, 2, 3) -Max-Constraint-Assignment-3-partite / Change.^[19]
  • (2, 3, 6) -Max-Constraint-Assignment-2-partite / Change bylo prokázáno, že je PLS-úplné díky těsné redukci PLS z Circuit / Flip na (2, 3, 6) -Max-Constraint-Assignment-2-partite / Change.^[19]
  • (6, 2, 2) -Max-Constraint-Assignment / Change bylo prokázáno, že je PLS-úplné díky těsné redukci z Circuit / Flip na (6,2, 2) -Max-Constraint-Assignment / Change.^[19]
  • (4, 3, 3) -Max-Constraint-Assignment / Change rovná se Max-4Sat- (B = 3) / Flip a bylo prokázáno, že je PLS-kompletní prostřednictvím redukce PLS z Max-circuit / Flip.^[13] Tvrdí se, že redukci lze prodloužit, aby se dosáhlo těsnosti.^[19]
• Nejbližší barevný polytop / změna bylo prokázáno, že je PLS kompletní díky redukci PLS z Max-2Sat / Flip na Nearest-Colorful-Polytope / Change.^[3]
• Stabilní konfigurace / převrácení v Hopfieldova síť bylo prokázáno, že je PLS-úplné, pokud jsou prahové hodnoty 0 a váhy jsou záporné prostřednictvím těsné redukce PLS z Max-Cut / Flip na Stable-Configuration / Flip.^[1][8][16]
• Vážené-3D-dimenzionální-shody / (p, q) - Výměna bylo prokázáno, že je PLS-kompletní pro p ≥9 a q ≥ 15 prostřednictvím těsné redukce PLS z (2, 3, r) -Max-Constraint-Assignment-2-partite / Change to Weighted-3Dimensional-Matching / ( p, q) - Výměna.^[5]

Reference

• Yannakakis, Mihalis (2009), „Rovnováhy, pevné body a třídy složitosti“, Recenze informatiky, 3 (2): 71–85, CiteSeerX  10.1.1.371.5034, doi:10.1016 / j.cosrev.2009.03.004.