PLS(복잡성)

계산 복잡성 이론에서 PLS(Polyomial Local Search, PLS)는 최적화 문제에 대한 국소적으로 최적의 솔루션을 찾는 어려움을 모델링하는 복잡성 등급이다.PLS에 존재하는 문제의 주요 특징은 다항 시간대에 솔루션 비용을 계산할 수 있고 다항 시간대에 솔루션 주변을 검색할 수 있다는 것이다.따라서 다항식 시간에 솔루션이 국소 최적인지 여부를 확인할 수 있다.나아가 문제해결에 사용되는 알고리즘과 문제에 따라 글로벌 최적점 대신 국소 최적점을 찾는 것이 더 빠를 수 있다.

설명

지역 최적화를 검색할 때 처리해야 할 두 가지 흥미로운 문제가 있다.첫째, 지역 최적점을 찾는 방법과 둘째, 지역 최적점을 찾는 데 걸리는 시간이다.많은 로컬 검색 알고리즘의 경우 다항식 시간에 로컬 최적값을 찾을 수 있는지 여부는 알 수 없다.^[1]그래서 지역적 최적점을 찾는 데 얼마나 시간이 걸리는가에 대한 질문에 답하기 위해 존슨, 파파디미트리오, 얀나카키스는 "지역적 검색이 얼마나 쉬운가?"라는 논문에서 복잡도 등급 PLS를 소개했다.다항식 시간에 로컬 최적성을 검증할 수 있는 로컬 검색 문제를 포함하고 있다.

다음 속성이 충족되는 경우 로컬 검색 문제가 PLS에 있다.

• 모든 솔루션의 크기는 인스턴스 $I{\displaystyle }$ ${\displaystyle I}$의 크기로 다항식으로 제한된다$.$
• 다항식 시간 내에 문제 사례의 해결책을 찾을 수 있다.
• 다항식 시간 내에 각 솔루션의 비용을 계산할 수 있다.
• 다항식 시간에 각 해결책의 모든 이웃을 찾을 수 있다.

이러한 속성을 통해 각 솔루션 $s{\displaystyle }$ ${\displaystyle s}$에 대해 최상의$$ 인접 솔루션을 찾을 수 있거나 더 나은 인접 솔루션이 없는 경우 $s{\displaystyle }$ ${\displaystyle s}$이(가) 현지 최적 솔루션임을$$ 명시할 수 있다.

예

Consider the following instance ${\displaystyle I}$ of the Max-2Sat Problem: ${\displaystyle (x_{1}\vee x_{2})\wedge (\neg x_{1}\vee x_{3})\wedge (\neg x_{2}\vee x_{3})}$.그 목적은 과제를 찾는 것인데, 이는 만족한 조항의 합을 최대화하는 것이다.

해당 인스턴스에 대한$$ $솔루션{\displaystyle }$ s ${\displaystyle s}$은(는) 모든 $x{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$ 값을$$ 0 또는 1로 할당하는 비트 문자열이다.이 경우 솔루션은 3비트로${\displaystyle \mathrm{구성}}$되는데$,$ 예를 $들어$ s = 000 {\displaystyle $s=000$은 값이 0인$$ $x{\displaystyle {}_{}}$ 1 ${\$}에 x ${\displaystyle {1\mathrm{}}_{}}$ ${\$을 할당하는 것을 의미한다.솔루션 $F{\displaystyle {}_{}}$ ${\displaystyle L{}_{}}$( I${\displaystyle }$) ${\displaystyle F_{L}(I)}$의 세트는 $x$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$}:{1$\},$ ${\displaystyle {x\mathrm{}}_{}}$ 2 ${\$}} 및$$ $x{\displaystyle {}_{}}$ ${\displaystyle {3\mathrm{}}_{}}$ ${\$의 가능한 모든 할당 집합이다.

각 해결책의 비용은 만족하는 절의 수이기 $때문$에, c ${\displaystyle L_{}}$(${\displaystyle I}$, ${\displaystyle s}$= ${\displaystyle 000}$)${\displaystyle }$= ${\displaystyle 2}$ ${\displaystyle c_{L}(I,s=000)=2}$이(가)는 제2절과 제3절이 만족되기 때문이다$$.

솔루션 $s{\displaystyle }$ ${\displaystyle$ s$}$의 플립네이버는 비트 $문자열{\displaystyle }$ s ${\displaystyle s}$의 한 비트를 플립하면 도달하므로$,$ $s{\displaystyle }${\$displaysty$s}의 이웃은 $다음$과 같은 비용으로$$ N${\displaystyle (}$ I${\displaystyle }$, ${\displaystyle 000}$)${\displaystyle }$=${\displaystyle }${ $,$ ${\displaystyle 010,}$ $}{\displaystystyle$ N$(I$,000$)=\100,010,001\}$이다.

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

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

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

최대 비용으로 솔루션을 찾고 있다면 $s{\displaystyle }$ ${\displaystyle s}$보다 더 나은 비용을 가진 이웃은 없다$.$$s{\displaystyle }$ ${\displaystyle s}$이(예: 모든 조항을 충족하고 ${\displaystyle \mathrm{c}}$ ${\displaystyle L_{}I}$, ${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$)${\displaystyle }$= 3 ${\displaystyle c_{L}(I,s')=3}$을(를) 갖는$$ $솔루션{\displaystyle {}^{}}$ s ${\displaystyle {\prime }^{}}$=$111이$되더라도,$$ $s{\displaystyle }$ ${\displaysty s}$은 주변 어느 쪽도 더 나은 비용을 가지고 있지 않기 때문에 현지$$ 최적이다.

직관적으로 이 문제가 PLS에 있다고 주장할 수 있는 이유는 다음과 같다.

• 예를 들어 모든 비트를 0으로 설정하여 다항식 시간 내에 인스턴스에 대한 솔루션을 찾을 수 있다.
• 다항 시간 내에 해결책의 비용을 계산하는 것은 전체 인스턴스를 한 번 훑어보고 충족되는 절을 세어 보는 것이 가능하다.
• $s{\displaystyle }$ ${\displaystyle s}$과(와) 다른 솔루션 집합을 정확히 한 비트 안에$$ 취함으로써 다항식 시간에 솔루션의 모든 인접 항목을 찾을 수 있다.

형식 정의

A local search problem ${\displaystyle L}$ has a set ${\displaystyle D_{L}}$ of instances which are encoded using strings over a finite alphabet ${\displaystyle \Sigma }$. For each instance ${\displaystyle I}$ there exists a finite solution set ${\displaystyle F_{L}(I)}$. Let ${\displ$$aystyle R}$ be the relation that models ${\displaystyle L}$. The relation ${\displaystyle R\subseteq D_{L}\times F_{L}(I):=\{(I,s)\mid I\in D_{L},s\in F_{L}(I)\}}$ is in PLS ^{[2] [3][4]} if:

• 모든 솔루션의 $크기{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle {}_{}}$ ${\displaystyle L_{}}$( ${\displaystyle I}$) ${\displaystyle s\in F_{L}(I)}$은(는) $I{\displaystyle }$ ${\displaystyle I}$ 크기로 다항식 경계로 지정됨$$
• 문제 인스턴스 $I{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle D_{}}$ ${\displaystyle {}_{}}$ ${\$ 및 $솔루션$ ${\displaystyle \in }$ F ${\displaystyle {}_{}}$(${\displaystyle I}$) ${\displaystyle s\in F_{L}(I)}$은 다항식 시간 검증 가능$$
• 다항식 시간 계산 함수 $A{\displaystyle }$: ${\displaystyle {}_{}}$ ${\displaystyle L_{}}$→ ${\displaystyle {}_{}}$ ${\displaystyle L_{}}$( ${\displaystyle I}$ )${\displaystyle A:$각 인스턴스 $I{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle D_{}}$ L ${\$에 대해 반환되는$$ $D_{L}\{L}\{$$displaystyle s\in F_{L}}}$ 일부 솔루션$$ $s{\displaystyle }$∈ ${\displaystyle F_{}}$ L ($I)$
• ${\displaystyle {\mathbb{}}^{}}$ 시간 계산 함수 $B{\displaystyle }$: D ${\displaystyle L_{}}$ ${\displaystyle {}_{}}$ F ${\displaystyle L_{}}$( ${\displaystyle I}$)${\displaystyle }$→ R${\displaystyle {}^{}}$+ ${\$$D_{L}\times F_{L}(I)\rightarrow \mathbb {R} ^{+}}$ ^[5] that returns for each solution ${\displaystyle s\in F_{L}(I)}$ of an instance ${\displaystyle I\in D_{L}}$ the cost ${\displaystyle c_{L}(I,s)}$
• 다항식 시간 계산 함수 $N{\displaystyle }$: ${\displaystyle {}_{}}$ ${\displaystyle L_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle F_{}}$ ${\displaystyle L{}_{}}$( I${\displaystyle }$)${\displaystyle }$→ ${\displaystyle P}$ ${\displaystyle o}$ ${\displaystyle o}$ e ${\displaystyle e}$ s e ${\displaystyle t}$( ${\displaystyle {}_{}}$ ${\displaystyle L_{}}$( ${\displaystyle I}$)${\displaystyle$ N$:$인스턴스-솔루션 쌍에 대해 인접 집합을 반환하는$$ $D_{L}(I)\오른쪽 화살표 Powerset(F_{L}(I)}$
• 다항식 시간 계산 함수 $C{\displaystyle }$: ${\displaystyle {}_{}}$ ${\displaystyle L_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle F_{}}$ ${\displaystyle L{}_{}}$( I${\displaystyle }$)${\displaystyle }$→ ${\displaystyle N}$( ${\displaystyle I}$, ${\displaystyle s}$) ${\displaystyle \cup }${ O ${\displaystyle P}$ ${\displaystyle T}$ ${\displaystyle \}}$ ${\displaystyle C:$솔루션$$ $s{\displaystyle }$ ${\displaystyle s$보다 더 저렴한 비용으로$$ 인접 솔루션 $s{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$을(를) 반환하거나 $s{\displaystyle }$ ${\displaystyle s}$이(가) 로컬로$$ 최적임을 나타내는 $D_{L}(I)\$rightarrow N$(I,s)\optp\}컵\}}$
• 모든 $인스턴스{\displaystyle }$ I ${\displaystyle \in }$ ${\displaystyle D_{}}$ ${\displaystyle {}_{}}$ ${\$에 대해$,$ $R{\displaystyle }${\$displaystyle R}$은(는) 쌍${\displaystyle (I}$ ,${\displaystyle s}$ )$${\$displaystyle(I,s)$을 정확히 포함하고 있으며, $여기$서 s$${\$displaystyle$s}은 I$}$의 로컬 최적 $솔루션$이다.

An instance ${\displaystyle D_{L}}$ has the structure of an implicit graph (also called Transition graph ^[6]), the vertices being the solutions with two solutions ${\displaystyle s,s'\in F_{L}(I)}$ connected by a directed arc iff ${\displaystyle s'\in N(I,s)}$.

현지 최적화는 $더{\displaystyle }$ 나은 비용을$$가진 이웃이 없는 $솔루션$ s {\displaystyle $s}$이다$.$암묵적 그래프에서 국소 최적치는 싱크다.모든 지역 최적화가 글로벌 최적화가 되는 동네를 가장 좋은 비용으로 해결해주는 동네라고 한다.^[6][1]

대체 정의

클래스는 PLS는 클래스는 다항 시간의 문제 Sink-of-DAG[7](또한 Local-Opt[8]을 불렀다)으로 줄어들 수 있는지 모든 문제점을 감안할 때 두개의 정수를 n{n\displaystyle}과 m{m\displaystyle}와 두 부울 논리 연산 회로 S포함하는:{0,1}n→{0,1}n{\displaystyle S:\와 같이{0,1\}^{n}\rightarrow \{0,1\}^{n}}.such that ${\displaystyle S(0^{n})\neq 0^{n}}$ and ${\displaystyle V:\{0,1\}^{n}\rightarrow \{0,1,..,2^{m}-1\}}$, find a vertex ${\displaystyle x\in \{0,1\}^{n}}$ such that ${\displaystyle S(x)\neq x}$ and either ${\displaystyle S(}$${\displaystyle S}$${\displaystyle }$(${\displaystyle x}$)${\displaystyle }$= ${\displaystyle S}$( x${\displaystyle }$) ${\displaystyle S(S)(x)=S($${\displaystyle x}$$)}$ 또는$$ $V{\displaystyle }$ (${\displaystyle }$S (${\displaystyle x}$)${\displaystyle \le }$ V${\displaystyle }$( ${\displaystyle x}$) ${\displaystyle V(S)(x)\leq$ V$(x$

주변 구조 예제

솔루션으로 부울 변수(또는 비트 문자열)를 사용하는 문제에 대한 주변 구조 예:

• Flip[2]-해결책의 주변은 cmx1,,)n{\displaystyle s=x_{1},...,x_{n}}나는{\displaystyle x_{나는}(이놈의)한 임의의 입력 비트=}을 부정하는.{\displaystyle r\in N(I,s)}dist 해밍이 있는 하나의 해결책 s{s\displaystyle}과 모든 그것의 이웃들이었고 넌 결코 모르네∈ N(나는, 투쟁 경력)달성할 수 있다.ance 1: $H{\displaystyle }$( ${\displaystyle s}$, ${\displaystyle r}$)${\displaystyle }$= ${\displaystyle 1}$ ${\displaystyle H(s,r)=1$
• Kernighan-Lin^[2][6] - 일련의 탐욕스러운 플립으로 r$$ ${\displaystyle r$$}$을(를) $얻을{\displaystyle }$ 수 있는$$ 경우$$ $솔루션{\displaystyle }$ r$${\$displaystyle$$s$$}$의 인접 항목이며, 여기서$$ 비트는 두 번 뒤집히지 않는다.즉$,$ $s{\displaystyle }$ ${\displaystyle s}$부터 최상의 비용 또는 최소 비용 손실이 있는$$ ${\displaystyle s}$의 플립-근접 ${\displaystyle {s\mathrm{}}_{}}$ 1 ${\$}를 Kernighan-Lin 구조에서 s의 인접자로 선택한다.$s{\displaystyle {}_{}}$ ${\$등의 최상(또는 최소 최악의) 이웃뿐 아니라, $s{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$까지 s ${\displaysty s}$의 모든 비트가 부정되는$$ 솔루션이다$$.한 번 뒤집힌 경우에는 뒤로 약간 뒤집으면 안 된다는 점에 유의하십시오.
• k-플립^[9] - 해밍 거리 $H {\displaystyle$ $r$$}$과($와{\displaystyle }$) r ${\displaystyle r$$}$ 사이의$$ Hamming 거리 H ${\displaystyle$ H$}$이$($$)$ 최대 $k{\displaystyle }$ ${\$$displaystystyle k$인 ${\displaystyle \mathrm{경우}}$ $솔루션$${\displaystyle }$r ${\displaystystyle s}$의 인접함$.$

그래프의 문제에 대한 주변 구조 예:

• 칸막이(20, P1){\displaystyle(P_{0}일 경우 ,P_{1})}의 Swap[10]-노드의 그래프에서 파티션(P2, P3){\displaystyle(P_{2},P_{3})}는 이웃 만약(P2, P3){\displaystyle(P_{2},P_{3})}(20, P1){\displaystyle(P_{0}일 경우 ,P_{1})}에서 얼마나 자주'o'를 교환하며 얻을 수 있nneOde $p{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$∈ P ${\displaystyle {0\mathrm{}}_{}}$ ${\$}\in P_{0$}}$에 노드 $p{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$$1$}}.
• Kernighan-Lin[1][2]-(20, P1){\displaystyle(P_{0}일 경우 ,P_{1})}의 노드와 파티션(P2, P3){\displaystyle(P_{2},P_{3})}는 이웃 만약(P2, P3){\displaystyle(P_{2},P_{3})}스와프 거래는 한 욕심 많은 순서에 의해 노드에서 P0{\displaystyle P_{0}으로 얻을 수 있}에. P1${\displaystyle P_{1$This means the two nodes ${\displaystyle p_{0}\in P_{0}}$ and ${\displaystyle p_{1}\in P_{1}}$ are swapped, where the partition ${\displaystyle ((P_{0}\setminus p_{0})\cup p1,(P_{1}\setminus p_{1})\cup p_{0})}$ gains the highest가능한 무게 또는 가능한 최소의 무게를 감소시킨다.어떤 노드도 두 번 스왑할 수 없다는 점에 유의하십시오.
• Fiducia-Matheys - 이 동네는 Kernighan-Lin 동네 구조와 유사하며, 각각의 스왑이 두 단계로 이루어진다는 점을 제외하면 욕심 많은 스왑 순서다.First the ${\displaystyle p_{0}\in P_{0}}$ with the most gain of cost, or the least loss of cost, is swapped to ${\displaystyle P_{1}}$, then the node ${\displaystyle p_{1}\in P_{1}}$ with the most cost, or the least loss of cost is swapped to ${\displaystyle P_{0}}$ to ba칸막이를 다시 걸다실험 결과, Fiducia-Mattheys는 때때로 열등한 국소 최적값을 찾기도 하지만 표준 알고리즘의 각 반복에서 실행 시간이 더 짧다는 것이 밝혀졌다.
• FM-Swap^[1] - 이 동네 구조는 피두치아-마테이스 근린 구조를 기반으로 한다.각 솔루션 $s{\displaystyle }$=${\displaystyle }$( ${\displaystyle {P\mathrm{}}_{}}$ 0${\displaystyle {}_{}}$, P ${\displaystyle {1\mathrm{}}_{}}$) ${\displaystyle$ s$=(P_{0},P_{1})$에는 Fiducia-Mattheys의 첫 번째 스왑 후에 얻은 파티션인 하나의 인접 파티션만 있다$$.

표준 알고리즘

다음 계산 문제를 고려하십시오.Given some instance ${\displaystyle I}$ of a PLS problem ${\displaystyle L}$, find a locally optimal solution ${\displaystyle s\in F_{L}(I)}$ such that ${\displaystyle c_{L}(I,s')\geq c_{L}(I,s)}$ for all ${\displaystyle s'\in N(I,s)}$.

모든 로컬 검색 문제는 다음과 같은 반복 개선 알고리즘을 사용하여 해결할 수 있다.^[2]

1. $초기{\displaystyle {}_{}}$ 솔루션 $s{\displaystyle }$ ${\$$displaystyle A_{L}$를 찾으려면$$ A ${\displaystyle L_{}}$ ${\$$displaystyle s}$을(를) 사용하십시오.
2. 알고리즘 $C{\displaystyle {}_{}}$ ${\displaystyle L_{}}$ ${\$ $C_$${L}$을 ${\displaystyle \mathrm{사용}}$하여 더 나은 솔루션 $s{\displaystyle {}^{}}$ ${\displaystyle \prime }$ ${\displaystyle N}$ ( I${\displaystyle }$,${\displaystyle }$s${\displaystyle }$) ${\displaystyle$ s$'\in N(I,s$)}을$($를) 찾으십시오$.$ 이러한 솔루션이 존재하면 s ${\displaystyle$ $s}$을(를) $s{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$$displaystyty$)로 교체하고$$ 2단계를 $반복$하십시오$.$

불행히도, 다항식 시간에 정확히 $문제{\displaystyle }$ L ${\displaystyle L}$을(를) 해결할 수 있더라도$$ 국소 최적점을 찾으려면 일반적으로 기하급수적인 개선 단계가 필요하다.^[2]표준 알고리즘을 항상 사용할 필요는 없으며, 특정 문제에 대해 다른, 빠른 알고리즘이 있을 수 있다.예를 들어 선형 프로그래밍에 사용되는 로컬 검색 알고리즘은 Simplex 알고리즘이다.

표준 알고리즘의 실행 시간은 솔루션의 서로 다른 비용 수에서 유사 폴리노믹이다.^[12]

표준 알고리즘에 필요한 공간은 다항식일 뿐이다.정의에 의해 제한된 다항식인 현재 $솔루션{\displaystyle }$ s ${\displaystyle s$만 저장하면 된다.^[1]

할인

한 문제를 다른 문제로 축소하는 것은 두 번째 문제가 적어도 첫 번째 문제만큼 어렵다는 것을 보여주기 위해 사용될 수 있다.특히 PLS완전성 문제를 PLS완전성이 입증되어야 하는 문제로 축소함으로써 PLS에 있는 국지적 검색 문제도 PLS완전성이라는 것을 입증하기 위해 PLS 감소를 사용한다.

PLS 감소

로컬^[2]$$ 검색 문제 ${\displaystyle {L\mathrm{}}_{}}$ $1{\displaystyle {}_{}}$ ${\$}은$$(는) 로컬 검색 문제 ${\displaystyle {L\mathrm{}}_{}}$ 2 ${\$ 다항식 시간 함수 $f{\displaystyle }$: ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$→ ${\displaystyle {D\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\$$D_{1}\$오른쪽 $화살표 D_{2$}}$$및 $g$ : D ${\displaystyle {1\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$( ( (${\displaystyle {I\mathrm{}}_{}}$ 1${\displaystyle }$)${\displaystyle }$→ ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$( ${\displaystyle {I\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ $){\displaystyle$ g$:$$D_{1}\times F_{2}(f(I_{1})\오른쪽$ 화살표 $F_{$1$$$}(I_{1}):$

• $I{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$}이$$ ${\displaystyle {L\mathrm{}}_{}}$ 1 ${\$}의 인스턴스인 경우,$$ $f{\displaystyle }$( ${\displaystyle {I\mathrm{}}_{}}$ 1${\displaystyle {}_{}}$) ${\displaystyle f(I_{1})$는 $L{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$}의 인스턴스인 경우
• if ${\displaystyle s_{2}}$ is a solution for ${\displaystyle f(I_{1})}$ of ${\displaystyle L_{2}}$ , then ${\displaystyle g(I_{1},s_{2})}$ is a solution for ${\displaystyle I_{1}}$ of ${\displaystyle L_{1}}$
• if ${\displaystyle s_{2}}$ is a local optimum for instance ${\displaystyle f(I_{1})}$ of ${\displaystyle L_{2}}$ , then ${\displaystyle g(I_{1},s_{2})}$ has to be a local optimum for instance ${\displaystyle I_{1}}$ of ${\displaystyle L_{1}}$

$f{\displaystyle ({}_{}}$ $){\displaystyle f(I_{1})$의 로컬 최적만 ${\displaystyle I_{}}$ $1\{\backslash$$displaystyle I_{$1}의 로컬 최적에만 매핑하고, 예를 들어 다른 모든 솔루션을 $A{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$}에 의해 반환된 표준 솔루션에 매핑하면 충분하다$.$^[6]

PLS 감소는 타동적이다.^[2]

엄격한 PLS 감소

정의 전환 그래프

전환 그래프^[6] ${\displaystyle T_{}}$ $I{\displaystyle {}_{}}$ ${\$문제 $L{\displaystyle }$ ${\displaystyle L}$ 인스턴스$$ $I{\displaystyle }$ ${\displaystyle I}$의 I$}$은(는) 방향 그래프입니다.노드는 유한한 ${\displaystyle {솔루션}_{}}$ ${\displaystyle F}$ L ${\displaystyle {}_{}}$I${\displaystyle }$) {\$displaystyle F_{L}($I)}의 모든 요소를 나타내며$$, 한 솔루션에서 엄격히 더 나은 비용으로 인접 솔루션으로 가는 가장자리 지점을 나타낸다.그러므로 그것은 순환 그래프다.싱크대(sink)는 출구에 가장자리가 없는 노드로서 국소.꼭지점 $v{\displaystyle }$ ${\displaystyle v}$의 높이는 $v{\displaystyle }$ ${\displaystyle v}$에서 가장 가까운 싱크까지$$ 최단 경로의 길이입니다$$.전환 그래프의 높이는 모든 정점의 높이 중 가장 크므로 노드에서 가장 가까운 싱크까지 가능한 가장 짧은 경로의 높이다.

정의 엄격한 PLS 감소

지역 탐색 문제에서 온 PLS-reduction(f, 감속){\displaystyle(f,g)}L1{\displaystyle L_{1}}는 국내 검색 문제에 L2{\displaystyle L_{2}}은 견고한 PLS-reduction[10] 예를 들어, 제가 1}나는 1{\displaystyle L_{1}의{\displaystyle I_{1}}, 하위 집합 R{R\displaystyle}. 의$인스턴스$ $I{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$= f${\displaystyle }$( ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$) ${\displaystyle I_{2}=f(I_$${1})$의 솔루션을 선택하여$$ 다음과 같은 ${\displaystyle {속성}_{}}$을$$충족할 수 $있다$.

• ${\displaystyle R}$ ${\displaystyle R}$에는 다른 솔루션 중에서도 I$$ {\$displaystyle I_{2$}의 모든 로컬 최적화가 포함되어$$ 있음
• For every solution ${\displaystyle p}$ of ${\displaystyle I_{1}}$ , a solution ${\displaystyle q\in R}$ of ${\displaystyle I_{2}=f(I_{1})}$ can be constructed in polynomial time, so that ${\displaystyle g(I_{1},q)=p}$
• If the transition graph ${\displaystyle T_{f(I_{1})}}$ of ${\displaystyle f(I_{1})}$ contains a direct path from ${\displaystyle q}$ to ${\displaystyle q_{0}}$, and ${\displaystyle q,q_{0}\in R}$, but all internal path vertices are outside ${\displaysty$$le R}$, then for the corresponding solutions ${\displaystyle p=g(I_{1},q)}$ and ${\displaystyle p_{0}=g(I_{1},q_{0})}$ holds either ${\displaystyle p=p_{0}}$ or ${\displaystyle T_{$$I_{1}:{$1}}에는$$p {\$displaystyle$p}에서 p$$0 {\$displaystyle p_${0$$$}$까지의 에지가$$ 포함되어 있음

다른 복잡성 클래스와의 관계

PLS는 P와 NP의 기능 버전 사이에 위치한다: FP ⊆ PLS ⊆ FNP.^[2]

PLS도 TFNP의 서브클래스로, 솔루션이 존재한다고 보장되고 다항 시간 내에 인식될 수 있는 연산 문제를 기술하고 있다.^[13]PLS의 문제에 대해서는, 전체 그래프의 최소 비용 정점이 유효해, 해결책의 유효성은 그 이웃을 계산하고 각각의 비용을 서로 비교함으로써 확인할 수 있기 때문에, 해결책이 존재한다고 보증한다.

또한 PLS 문제가 NP-hard인 경우 NP = co-NP인 것으로 입증된다.^[2]

PLS-완전성

정의

로컬 검색 문제 $L{\displaystyle }$ ${\displaystyle L}$은(는)^[2] PLS 완료임

• ${\displaystyle L}$ ${\displaystyle L}$이(가) PLS에 있음
• PLS의 모든 문제는 $PLS$를 L ${\displaystyle L}($으)로 줄일 수 있음

Flip neighborhood 구조에서 회로 문제의 최적화 버전은 첫 번째 PLS 완료 문제로 나타났다.^[2]

PLS 완료 문제 목록

이것은 PLS-완전한 몇몇 알려진 문제의 불완전한 목록이다.

표기법: 문제 / 근린구조

• 최소/최대 회로/플립이 첫 번째 PLS 완료 문제로 입증되었다.^[2]
• DAG 싱크는 정의상 완전하다.
• 모든 것이 같지 않은 양의 최대 3Sat/플립은 최소/최대 회로/플립에서 모두 같지 않은 양의 최대 3Sat/플립으로 엄격한 PLS 감소를 통해 PLS 완성이 입증되었다.Positive-not-all-equal-max-3Sat/Flip도 Max-Cut/Flip에서 줄일 수 있다는 점에 유의하십시오.^[10]
• 모든 것이 같지 않은 양의 최대 3Sat/Kernighan-Lin은 Min/Max-Circuit/Flip에서 Positive-notal-Max-3Sat/Kernighan-Lin으로 엄격한 PLS 감소를 통해 PLS 완성이 입증되었다.^[1]
• Max-2Sat/Flip은 Max-Cut/Flip에서 Max-2Sat/Flip으로 엄격한 PLS 감소를 통해 PLS 완성이 입증되었다.^[1][10]
• Min-4Sat-B/플립은 Min-Sat-B/플립에서 Min-4Sat-B/플립으로 엄격한 PLS 감소를 통해 PLS 완성이 입증되었다.^[9]
• 최대 4Sat-B/플립(또는 CNF-SAT)은 최대 회로/^[14]플립에서 최대 4Sat-B/플립으로 PLS 감소를 통해 PLS 완성이 입증되었다.
• 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-Grape-Partitioning/Swap으로 엄격한 PLS 감소를 통해 PLS 완성이 입증되었다.^[10]
• Max-Uniform-Graph-Partitioning/Fiduccia-Matheys는 증거 없이 PLS-완전하다고 명시되어 있다.^[1]
• Max-Uniform-Graph-Partitioning/FM-Swap은 Max-Cut/Flip에서 Max-Uniform-Grappitioning/FM-Swap으로 엄격한 PLS 감소를 통해 PLS 완성이 입증되었다.^[10]
• Max-Uniform-Graph-Partitioning/Kernighan-Lin은 Min/Max-Max-Circuit/Flip에서 Max-Uniform-Graph-Partitioning/Kernighan-Lin으로 PLS 감소를 통해 PLS 완성이 입증되었다.^[2]Positive not-all-equal-max-3Sat/Kernighan-Lin에서 Max-Uniform-Graph-Partitioning/Kernigan-Lin까지 PLS 감소가 빠듯하다.^[1]
• Max-Cut/Flip은 PLS 완성을 통해 PLS 완성을 입증했다. Positive-notal-max-3Sat/Flip에서 Max-Cut/^[1][10]Flip까지.
• Max-Cut/Kernighan-Lin은 증거 없이 PLS 완성이라는 주장이 있다.^[6]
• Min-독립형-Domating-Set-B/k-Flip은 Min-4Sat-B'/Flip에서 Min-독립형-Setting-B/k-Flip으로 엄격한 PLS 감소를 통해 PLS 완성이 입증되었다.^[9]
• 가중 독립적인 설정/변경은 증거 없이 PLS 완료라고 주장된다.^[2][10][6]
• 최대 가중치-속성이 있는 서브그래프-속성이 있는-P/변경이 PLS-완료인 경우 속성 P = "에지가 없는" 경우, 가중 독립된 설정/변경과 같기 때문이다.또한 가중 독립 설정/변경에서 최대 가중-하중-하중-속성-P/변경까지 PLS 절감을 통해 일반 유전형 비경쟁 속성 P에 대해서도 PLS 완성이 입증되었다.^[16]
• 세트 커버/k 변경은 (3, 2, r)-최대-콘스트레이트-어셈블리/세트 커버/k 변경으로 변경에서 엄격한 PLS 축소를 통해 각 k ≥ 2에 대해 PLS 완료임이 입증되었다.^[17]
• 미터법-TSP/k-변경(Max-4Sat-B/플립)에서 미터법-TSP/k-변경(Max-4Sat-B/플립)으로 PLS 축소를 통해 PLS 완성이 입증되었다.^[15]
• 미터법-TSP/Lin-Kernighan은 Max-2Sat/Flip에서 미터법-TSP/Lin-Kernighan으로 엄격한 PLS 감축을 통해 PLS 완성이 입증되었다.^[18]
• 로컬-다중 프로세서-스케줄링/k-변경은 가중-3차원 매칭/(p, q)-스왑에서 로컬-다중 프로세서 스케줄링/(2p+q) 변경으로 엄격한 PLS 감소를 통해 PLS 완성이 입증되었다. 여기서 (2p + q)^[5] ≥ 8.
• Selfish-Multi-Processor-Scheduling/k-change-with-property-t has been proven to be PLS-complete via a tight PLS-reduction from Weighted-3Dimensional-Matching/(p, q)-Swap to (2p+q)-Selfish-Multi-Processor-Scheduling/k-change-with-property-t, where (2p + q) ≥ 8.^[5]
• General-Consistion-Game/Change에서 순수한 Nash 평형을 찾는 것은 PLS 완성이 Positive-not-equal-max-3Sat/Flip에서 General-Consion-Game/Change로 엄격한 PLS 감축을 통해 입증되었다.^[19]
• 대칭적 일반-대칭적 일반-합성-게임/변화에서 순수한 나시 균형 발견은 비대칭적 일반-합성-게임/대칭적 일반-합성-게임/변화로 인한 엄격한 PLS 감축을 통해 PLS 완성이 입증되었다.^[19]
• 한 비대칭 Directed-Network-Congestion-Games/Change에 순수한 순수한 내쉬 균형을 찾는 것 Positive-not-all-equal-max-3Sat/Flip Directed-Network-Congestion-Games/Change[19]에 가서에서 2-Threshold-Games/Change Directed-Network-Congestion-Games/Chang까지 빠듯한 PLS-reduction을 통해 빠듯한 감소를 통해PLS-complete 되는 것이 입증되었다.e.[20]
• 비대칭 비간접망-공합성-게임/변화에서 순수한 나시 평형을 찾는 것은 2-임계-공합성-게임/ 비대칭 비간접망-공합성-게임/변화에서 엄격한 PLS 축소를 통해 PLS 완성이 입증되었다.^[20]
• 2-Threshold 게임/변경에서 순수한 나시 평형을 찾는 것은 Max-Cut/Flip에서 2-Threshold 게임/변경으로의 엄격한 축소를 통해 PLS 완성이 입증되었다.^[20]
• 시장-공유-게임/다항식 비용에 따른 변화에서 순수한 나시 균형 발견은 2-스스로홀드 게임/시장-공유-게임/변화에 따른 엄격한 PLS 감축을 통해 PLS 완성이 입증되었다.^[20]
• Overlay-Network-Design/Change에서 순수한 Nash 평형을 찾는 것은 2-Threshold-Games/Change to Overlay-Network-Design/Change를 통해 PLS 완성이 입증되었다.비대칭 방향-네트워크-콩제스티온-게임/변화의 증거와 유사하게, 감소가 빠듯하다.^[20]
• Min-0-1-Integer Programming/k-Flip은 Min-4Sat-B'/Flip에서 Min-0-1-Integer Programming/k-Flip로 엄격한 PLS 감소를 통해 PLS 완성이 입증되었다.^[9]
• Max-0-1-Integer Programming/k-Flip은 PLS가 Max-0-1-Integer Programming/k-Flip으로 축소되었기 때문에 PLS-완료라고 주장되지만, 증거는 누락되어 있다.^[9]
• (p, q, r)-최대-규정-배정
  • (3)-최대-규정-어셈블리-3-partite/변경은 회로/플립에서 (3, 2, 3)-최대-규정-assignment-3-partite/change로 엄격한 PLS 감소를 통해 PLS 완성이 입증되었다.^[21]
  • (2, 3, 6)-최대 컨스트레이트-Assignment-2-partite/변경은 회로/플립에서 (2, 3, 6)-최대 컨스트레이트-2-partite/change로 엄격한 PLS 감소를 통해 PLS 완성이 입증되었다.^[21]
  • (6, 2, 2)-최대 컨스트레이트-Assignment/Change는 회로/플립에서 (6,2, 2)-최대 컨스트레이트-Assignment/Change로 엄격한 감소를 통해 PLS-완전한 것으로 입증되었다.^[21]
  • (4, 3, 3)-최대-최소-규격-배정/변경은 Max-4Sat-(B=3)/플립과 같으며, 최대 회로/플립에서 PLS 감소를 통해 PLS 완료임이 입증되었다.^[15]그만큼 감액 연장이 가능해 빡빡함을 얻을 수 있다는 주장이다.^[21]
• 가장 가까운 색상-폴리토프/변경은 최대 2Sat/플립에서 가장 가까운 색상-폴리토프/변경으로 PLS 감소를 통해 PLS 완성이 입증되었다.^[3]
• Hopfield 네트워크의 Stabily-Configuration/Flip은 임계값이 0이고 Max-Cut/Flip에서 Stabily-Configuration/Flip으로 엄격한 PLS 감소를 통해 가중치가 음수인 경우 PLS-완전한 것으로 입증되었다.^[1][10][18]
• 가중치-3차원 매칭/(p, q)-스왑은 (2, 3, r)-최대-기존-배정-2-파티트/가중치-3차원 매칭/(p, q)-스왑으로의 변경으로부터 엄격한 PLS 축소를 통해 p for9 및 q 15에 대해 PLS 완성이 입증되었다.^[5]
• The problem Real-Local-Opt (finding the ɛ local optimum of a λ-Lipschitz continuous objective function ${\displaystyle V:[0,1]^{3}\rightarrow [0,1]}$ and a neighborhood function ${\displaystyle S:[0,1]^{3}\rightarrow [0,1]^{3}}$) is PLS-complete.^[8]
• K ≥ 2와 NK-모델/포인트-mutation이 지정한 생물학적 피트니스 환경에서 지역 피트니스 피크를 찾는 것은 Max-2SAT/플립에서 엄격한 PLS 감소를 통해 PLS 완성이 입증되었다.^[22]

참조

• Yannakakis, Mihalis (2009), "Equilibria, fixed points, and complexity classes", Computer Science Review, 3 (2): 71–85, CiteSeerX 10.1.1.371.5034, doi:10.1016/j.cosrev.2009.03.004.