격리 보조정리

이론 컴퓨터 과학에서 고립 보조정리(또는 분리 보조정리 보조정리)라는 용어는 해결책이 존재한다면 문제에 대한 해결책의 수를 1개로 줄이는 무작위화된 알고리즘을 말한다.이는 솔루션 공간이 비어 있지 않은 경우, 불가해한 확률로 정확히 하나의 솔루션이 이러한 추가 제약 조건을 만족하도록 무작위 제약 조건을 구성함으로써 달성된다.고립 레마는 발리안트-바지라니 정리, 계산 복잡성 이론에서 토다의 정리처럼 컴퓨터 과학에서 중요한 응용을 가지고 있다.

최초의 격리 보조정리기는 비록 그 이름 아래는 아니지만 발리안트&바지라니(1986)에 의해 도입되었다.이들의 격리 보조정리기는 무작위적인 수의 하이퍼플레인을 선택하며, 불가해한 확률로 선택한 하이퍼플레인과 고정된 비빈 솔루션 공간의 교차점에 정확히 하나의 요소가 포함된 특성을 가지고 있다.이는 Valiant-Vazirani의 정리를 보여주는 것으로 충분하다: 부울 공식에 대한 만족도 문제에서 부울 공식에 고유한 해결책이 있는지 여부를 탐지하는 문제까지 무작위화된 다항식 시간 감소가 존재한다.물뮬리, 바지라니 & 바지라니(1987)는 약간 다른 종류의 격리 보조정리기를 도입했다.여기서 용액 공간의 모든 좌표에는 일정한 범위의 정수에 임의의 중량이 할당되며, 그 속성은 불가해한 확률로 용액 공간에 최소 중량을 갖는 원소가 정확히 하나 있다는 것이다.이것은 최대 일치 문제에 대한 무작위화된 병렬 알고리즘을 얻는 데 사용될 수 있다.

문헌에는 다양한 환경에서 서로 다른 필요를 충족시키기 위해 더 강한 고립성 레마가 도입되었다.예를 들어 샤리, 로하트기 & 스리니바산(1993)의 격리 보조정리(1993)는 물뮬리 외와 비슷한 보증을 가지고 있지만, 무작위 비트를 적게 사용한다.지수 시간 가설의 맥락에서 칼라브로 외 연구. (2008) k-CNF 공식에 대한 격리 보조정리 입증.노암타샤마는^[1] 매개변수가 약간 강한 격리 보조마사를 부여하고, 무게 영역의 크기가 변수 수보다 작더라도 비교 결과를 제공한다.

물뮬리, 바지라니, 바지라니의 고립 보조정리

Lemma. Let ${\displaystyle n}$ and ${\displaystyle N}$ be positive integers, and let ${\displaystyle {\mathcal {F}}}$ be an arbitrary family of subsets of the universe ${\displaystyle \{1,\dots ,n\}}$. Suppose each element ${\displaystyle x\in \{1,\dots ,n\}}$ in the universe r정수 가중치 $w{\displaystyle }$( ${\displaystyle x}$) ${\displaystyle w(x)}$을(를) 사용하며$,$ ${\displaystyle \mathrm{각각}}$은 $\{{\displaystyle }$ $1$,${\displaystyle }$…${\displaystyle }$, ${\displaystyle N}$ ${\displaystyle \}}$ ${\displaystyle \{1,\dots,N\}$에서 독립적이고 균일하게 무작위로 선택된다$.$$F{\displaystyle \mathcal{}}$ ${\$에서 집합 S의 중량은 다음과 같이 정의된다$$.

$[\displaystyle ww(S)=\sum _{x\in S}w(x)\,}$

$그런{\displaystyle \mathcal{}}$ 다음 최소 ${\displaystyle 1}$- ${\displaystyle n}$/ N ${\displaystyle 1-n/N$ 확률로 모든 F ${\$$mathcal {F}$ 집합 중에서 최소 가중치를 갖는 $고유$한 집합이 F ${\$ {\$mathcal {F}$에 있다$.$

보조정리기가 $F{\displaystyle \mathcal{}}$ ${\$의 특성에 대해 전혀 가정하지 않는다는 것은 주목할 만한 사실이며$,$ $예$를 들어 F ${\$은(는) ${\displaystyle \mathrm{2n}{}^{}}$- 1 ${\displaystyle 2^{n}-1}-1$}의 비빈$$ 하위 집합을 모두 포함할 수 있다$$.$F{\displaystyle \mathcal{}}$$$ ${\$에서 각 세트의 중량이 평균 $1{\displaystyle \mathrm{}}$ ${\displaystyle$ 1$}$에서 ${\displaystyle N}$ ${\displaystyle nN}$ 사이에 있으므로$$ 각 가능한 중량의 집합은 $({\displaystyle {2n}^{}}$- ${\displaystyle 1}$)${\displaystyle }$/${\displaystyle }$(${\displaystyle N}$) $[\displaystystyle (2^{n}-1$)/($N)})})}$ 세트가$$ 있을 것이다.그래도 확률이 높으면 무게가 최소인 독특한 세트가 있다.

물물무리, 바지라니, 바지라니의 증거

원소 x를 제외한 모든 원소의 가중치를 고정했다고 가정합시다.그 다음 x의 w(x)가 α보다 크면 어떤 최소 중량 하위 집합에도 포함되지 않고, $w{\displaystyle }$( x${\displaystyle }$)${\displaystyle }$α ${\displaystyle \alpha }$ ${\displaystyle w(x)\leq \alpha$ $\}\}$일 경우, 일부 최소 중량 집합에 포함된다.또한 ( x)< $>$ <<\$displaystyle w(x)><\alpha$일 경우 모든 최소 중량 하위 집합은 x를 포함해야 한다(우리가 α에서 w(x)를 줄일 때 x를 포함하지 않는 집합은 중량이 감소하지 않지만 x를 포함하는 집합은 중량은 감소하지 않는다).따라서 최소 중량 부분 집합에 x가 포함되어 있는지 여부에 대한 모호성은 x의 무게가 그 임계값과 정확히 동일한 경우에만 발생할 수 있다. 이 경우 x를 "가수"라고 부를 것이다.이제 x의 문턱값은 다른 원소의 무게로만 정의되었기 때문에 w(x)와는 독립적이며, 따라서 w(x)가 {1, …, N}에서 균일하게 선택되기 때문에

${\displaystyle \Pr[x{\text{는 단수]=\Pr[w(x)=\alpha ]\leq 1/N}$

그리고 일부 x가 단수일 확률은 최대 n/N이다.단수가 없는 경우 고유한 최소 중량 하위 집합이 있기 때문에 보조정리기가 따른다.

비고: 일부 x에 임계값(즉, w(x)이 최소 가능한 값, 1을 얻더라도 최소 중량 하위 집합에 x가 없을 수 있으므로 보조정리기는 {${\displaystyle }${\$displaystyle \leq$}($$ =가 아닌)로 고정한다.

조엘 스펜서의 증거

조엘 스펜서(1995년)에 의한 상기 증빙의 재작성판이다.^[2]

집합의 요소 x에 대해 정의

${\displaystyle \alpha(x)=\min _{S\in {\mathcal {F},x\not \in S}w(S)-\min _{S},x\in S}w(S\setminus \x\})}$

$\alpha {\displaystyle (}$ ${\displaystyle x}$) ${\displaystyle \alpha(x)}$은(는) x 이외의 원소의 가중치에만 의존하며 w(x) 자체에는 의존하지 않는다는 점을 관찰하십시오.따라서 w(x)로$$$\alpha {\displaystyle (x}$) ${\displaystyle \alpha(x)}$의 값이 무엇이든 {1, …, N}에서 균일하게 선택된다. $\alpha {\displaystyle (x}$ ${\displaystyle )}$ ${\displaystyle \alpha(x)}$과 같을 확률은 최대 1/N이다.따라서 일부 x에 대해$$ $w{\displaystyle }$( ${\displaystyle x}$)${\displaystyle }$= ${\displaystyle \alpha }$( ${\displaystyle x}$) ${\displaystyle w(x)=\alpha (x)}$의 확률은 최대 n/N이다.

이제 $최소{\displaystyle \mathcal{}}$ 무게의$F$ {\displaystyle {\$mathcal {F}$에 A와 B 세트가 두 개 있으면 A\B에 X가 있으면

${\displaystyle {\begin{aligned}\alpha (x)&=\min _{S\in {\mathcal {F}},x\not \in S}w(S)-\min _{S\in {\mathcal {F}},x\in S}w(S\setminus \{x\})\\&=w(B)-(w(A)-w(x))\\&=w(x),\end{aigned}}}$

그리고 우리가 본 바와 같이, 이 사건은 최대 n/N의 확률로 일어난다.

예제/응용 프로그램

• 원래 적용은 그래프의 최소 가중치(또는 최대 가중치) 완벽한 일치였다.각 가장자리에는 {1, …, 2m}의 랜덤 가중치가 할당되며, $F{\displaystyle \mathcal{}}$ ${\$은(는) 완벽한 일치의 집합이므로$$ 적어도 1/2의 확률로 고유한 완벽한 일치가 존재한다.그래프의 Tutte 행렬에 있는$$ 각 불확정 x ${\displaystyle i_{}}$ j ${\$$displaystyle x_{ij}}$을(를) $2{\displaystyle {\mathrm{}}^{}}$ ${\displaystyle {{\mathrm{wi}}_{}}^{}}$ j {\$displaystyle 2^{w_{$ij}}로 교체할 때, 여기서$$ ${\displaystyle {wi}_{}}$ ${\displaystyle j_{}}${\$displaysty w_{ij}}}}$는 가장자리의 랜덤 가중치임을$$ 보여 줄 수 있으며, 나아가 매트릭스의 결정요인을 찾을 수 있다.
• More generally, the paper also observed that any search problem of the form "Given a set system ${\displaystyle (S,{\mathcal {F}})}$, find a set in ${\displaystyle {\mathcal {F}}}$" could be reduced to a decision problem of the form "Is there a set in ${\displaystyle {\mathcal {F}}}$ with total weight at대부분의 k?"예를 들어, 그것은 파파디미트리오와 얀나카키스가 제기하는 다음과 같은 문제를 해결하는 방법을 보여주었는데, (논문이 작성된 시점 현재) 결정론적 다항식 시간 알고리즘이 알려져 있지 않다: 그래프와 "빨간색"으로 표시된 가장자리의 부분집합을 주어진다면, 정확히 k개의 빨간 가장자리와 완벽하게 일치하는 것을 찾는다.
• 발리안트-바지라니 정리는 NP 완성 문제에 대한 고유한 해결책에 관한 것으로, 격리 보조정리법을 사용하는 보다 간단한 증거를 가지고 있다.이는 CLIQ에서 무작위 축소를 통해 입증된다.IMT2000 3GPP - UE to Unique-CLIK.^[3]
• 벤-데이비드, 초르&골드레이치(1989)는 평균 사례 복잡성을 위해 Valiant-Vazirani의 판단력 감소에 대한 증거를 사용한다.
• Avi Wigderson은 1994년 격리 보조정리기를 사용하여 NL에서 UL로 무작위 축소를 실시했고, 이에 따라 NL/폴리 ⊆L/폴리임을 증명했다.^[4]나중에 라인하르트와 알렌더는 NL/폴리 = UL/폴리라는 것을 증명하기 위해 격리 보조정리기를 다시 사용했다.^[5]
• 헤마스파안드라와 오기하라의 저서에는 일반화를 포함한 고립기법에 관한 장이 있다.^[6]
• 격리 보조정리기는 디지털 워터마크를 위한 계획의 기초로서 제안되었다.^[7]
• 특정 사례의 격리^[8] 보조정리 삭제 및 신원 테스트에 사용하는 작업이 진행 중이다.^[9]

메모들

참조

외부 링크

• 즐겨찾는 정리: 랜스 포트나우의 독특한 목격자
• 리차드 J. 립턴의 고립 보조정리