카프-립톤 정리

이 글은 대부분의 독자들이 이해하기에는 너무 기술적인 것일 수도 있다. 기술 세부 정보를 제거하지 않고 비전문가가 이해할 수 있도록 개선하십시오.(2014년 10월) (이 템플릿 메시지를 제거하는 방법 및 시기 학습)

복잡성 이론에서, Karp-Lipton 정리에서는 부울 만족도 문제(SAT)가 다항식 논리 게이트 수를 가진 부울 회로에 의해 해결될 수 있다면, 그 다음이라고 기술하고 있다.

${\displaystyle {\mathrm{\pi }}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$= ${\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ $displaystyle \Pi _{2}=\Sigma _{2}\,},$ 따라서$$ ${\displaystyle \mathrm{PH}}$= ${\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$. ${\$ {$PH} =\Sigma _{2}.\,}$

즉, 비결정론적 다항식 시간 문제의 클래스인 NP가 불균일한 다항식 시간 복잡성 클래스 P/poly에 포함될 수 있다고 가정한다면, 이 가정은 그 두 번째 수준에서 다항식 계층의 붕괴를 의미한다.그러한 붕괴는 가능성이 낮다고 믿기지 않기 때문에, 복잡성 이론가들은 일반적으로 SAT용 다항식 크기 회로 또는 다른 NP-완전한 문제에 대한 불연속성의 증거로 정리를 본다.그러한 회로가 존재하지 않는다는 증거는 P ≠ NP를 암시할 수 있다. P/poly는 무작위화된 다항 시간(Adleman의 정리)에서 해결할 수 있는 모든 문제를 포함하고 있기 때문에, 그 정리는 또한 무작위화의 사용이 NP 완성 문제에 대한 다항 시간 알고리즘으로 이어지지 않는다는 증거도 된다.

Karp-Lipton 정리는 1980년에 처음 그것을 증명했던 Richard M. Karp와 Richard J. Lipton의 이름을 따서 명명되었다. (그들의 원본 증거는 PH를 ${\displaystyle {3\mathrm{}}_{}}$\에 $붕괴시켰고 \Sigma _{3$ 그러나 Michael Sipser는 그것을 ${\displaystyle {2\mathrm{}}_{}}$ 2 {$${\$displaystyty \Sigma _{{{{}$로 개선했다.)$$

정리의 변형은 동일한 가정 하에서 MA = AM, PH가 S^P
₂ 복잡도 등급으로 붕괴된다고 명시한다.PSPACE 또는 일부 다른 복잡성 등급에 다항식 크기의 회로가 있다고 가정할 경우 더 강력한 결론이 가능하다. P/폴리 참조.NP가 BPP의 서브셋(P/poly의 서브셋)으로 가정되는 경우, 다항식 계층 구조는 BPP로 축소된다.^[1]만약 coNP가 NP/poly의 하위 집합으로 가정된다면, 다항식 계층 구조는 그것의 세 번째 수준으로 붕괴된다.

직감

SAT용 다항식 크기 회로가 존재할 뿐만 아니라 다항식 시간 알고리즘에 의해 구성될 수 있다고 가정해 보자.그렇다면 이 가정은 SAT 자체가 회로를 구성하고 이를 적용하는 다항 시간 알고리즘에 의해 해결될 수 있다는 것을 암시한다.즉, SAT를 위해 효율적으로 구성 가능한 회로는 더 강한 붕괴, 즉 P = NP로 이어질 수 있다.

이러한 회로가 존재한다는 Karp-Lipton 정리의 가정은 약하다.그러나 복잡도 등급 \ ${\$}}의 알고리즘이 SAT에 대한 올바른 회로를 추측하는 것은$$ 여전히 가능하다.복잡도 등급 \ ${\$}는 형태의 문제를 설명한다$$.

$\displaystyle \cHB x\forall y\;\cHB(x,y)}$

여기서 $\psi {\displaystyle }$ ${\displaystyle \psi}$은(는) 모든 다항식 시간 계산 가능한 술어다.이 술어에서 첫 번째 정량기의 실존적 힘을 사용하여 SAT의 정확한 회로를 추측할 수 있으며, 두 번째 정량기의 보편적 힘을 사용하여 회로가 올바른지 확인할 수 있다.이 회로를 추측하고 검증하면 클래스 ${\displaystyle {Ⅱ\mathrm{}}_{}}$ 2 ${\$}의 알고리즘을 다른 문제를 해결하는 서브루틴으로 사용할$$ 수 있다.

자기 축소성

Karp-Lipton 증거를 보다 자세히 이해하기 위해 회로 c가 특정 크기의 SAT 인스턴스(instance)를 해결하기 위한 올바른 회로인지 테스트하는 문제를 고려하고, 이 회로 테스트 문제가 $belongs{\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$}에 속함을 보여준다$.$즉, 모든 다항식 경계 z에 대해 V(c,z)가 참인 경우에만 c가 올바른 회로인 다항식 시간 계산 술어 V가 존재한다.

회로 c가 다음 두 가지 특성을 만족하는 경우 SAT에 적합한 회로임.

• s가 SAT의 인스턴스(instance)이고 x가 인스턴스(instance)의 솔루션인 모든 쌍(s,x)에 대해 c가 참이어야 한다.
• c가 참인 SAT의 모든 예에 대해 s는 반드시 해결할 수 있어야 한다.

이 두 속성 중 첫 번째 속성은 이미 class ${\$등급의 문제 형태에 있다$.$ 두 번째 속성을 검증하기 위해 SAT의 자기 축소성 속성을 사용한다.

자기 감소성은 SAT 인스턴스가 해결 가능한지 여부를 신속하게 테스트할 수 있다면 그 인스턴스에 대한 명시적인 해결책을 거의 빨리 찾을 수 있는 현상을 설명한다.인스턴스(instance)에 대한 해결책을 찾으려면 s에 입력되는 부울 변수 x 중 하나를 선택하고, s가_i x를 상수 i로 대체하여 형성된 공식을 나타내는 두 개의 작은 인스턴스(instance)를₀₁ 만든다.이 두 개의 작은 인스턴스(instance)가 구성되면 각각에 대한 해결 가능성 테스트를 적용하십시오.이 두 테스트 중 하나의 테스트에서 작은 인스턴스가 만족스러운 것으로 나타난다면 완전한 솔루션이 도출될 때까지 해당 인스턴스를 계속 해결하십시오.

SAT에 대해 올바른 회로의 두 번째 특성을 확인하기 위해 다음과 같이 자기 축소성을 사용하여 다시 작성한다.

• c가 참인 SAT의 모든 예에 대해, 위에서 설명한 자체 감소 절차는 s에 대한 유효한 해결책을 찾는다.

따라서 $\pi {\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$에서 c가 SAT 문제를 해결하는 데 유효한 회로인지 여부를$$ 테스트할 수 있다.

자세한 내용은 임의의 자체 축소성을 참조하십시오.

카르프-립톤 정리 증명

Karp-Lipton 정리는 다항 경계 정량자를 가진 부울 공식에 대한 결과로 재작성될 수 있다.$\pi {\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$}의 문제는 이 유형의 공식으로 설명되며$$ 구문은 다음과 같다.

$\displaystyle \phi =\forall x\back y\;\properties (x,y)}$

여기서 $\psi {\displaystyle }$ ${\displaystyle \psi$}은$($는) 다항식 시간 계산 가능한 술어다.Karp-Lipton 정리에서는 이러한 유형의 공식은 다항식 시간에 정량자가 반대 순서로 나타나는 등가 공식으로 변환될 수 있다고 기술하고 있다. 이러한 공식은 $\sigma {\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$ 부공식에 속한다.

${\displaystyle s(x)=\display y\;\display (x,y)}$

SAT의 한 예다.즉, c가 SAT에 유효한 회로인 경우 이 보조양식은 미정식 c(s(x)와 동일하다.따라서 $\varphi {\displaystyle }$ ${\displaystyle \pi }$의 전체 공식은 (유효한 회로 c가 존재한다고 가정했을 때) 공식과 동일하다$$.

$[\displaystyle \exists c\forall (x,z)\;V(c,z)\wedge c(s(x)\,},}$

여기서 V는 위에서 설명한 바와 같이 c가 자기저감성을 이용하여 정말로 유효한 회로인지 확인하는 데 사용되는 공식이다.이 등가식에는 원하는 대로 정량자가 반대 순서로 있다.따라서 Karp-Lipton 가정은 ${\displaystyle {existential2\mathrm{}}_{}}$= ${\displaystyle {\pi 2\mathrm{}}_{}}$. ${\displaystyle \Sigma _{2}=\Pi _{2}}}$전환 과정을 반복하면$$ 보다 깊은 보금자리를 가진 공식을 하나의 실존적 q를 갖는 형태로 단순화할 수 있다.uantifier에 이어 하나의 범용 계량기가 나타나 P ${\displaystyle H}$= ${\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$. ${\displaystyle PH=\Sigma _{2}.$$}$

또₂^P 다른 증거와 S

$N{\displaystyle \mathsf{}}$ ${\displaystyle \mathsf{P}}$ ${\displaystyle \subseteq }$ ${\displaystyle P\mathsf{}\mathsf{}}$/ ${\displaystyle p\mathsf{}}$ ${\displaystyle \mathsf{o}}$ ${\displaystyle \mathsf{y}}$ ${\$ {$NP}\subseteq {\mathsf {P/폴리}}$을(를) 가정해 보십시오$.$따라서 길이 n 입력 시 만족도를 해결하는$$ 회로 $C{\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$이 존재한다.자체 축소성을 사용하여 실제 인스턴스에 만족스러운 할당을 출력하는$$ 회로 $D{\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$ 계열이 존재한다.

L이 $\pi {\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$} 세트라고$$ 가정해 보십시오.

$L=\{z:\forall x.\exists y.\phi (x,y,z)\}\,}$

$\exists {\displaystyle \mathrm{}}$ ${\displaystyle y}$ .${\displaystyle \varphi }$( ${\displaystyle x}$, y${\displaystyle }$, ${\displaystyle z}$ )${\displaystyle \exists y.$$\phi(x,y,z)}$은(는) SAT의 한 인스턴스로 간주될 수 있다$$(Cook-Levin 정리), $n{\displaystyle }$= ${\displaystyle z}$ $displaystyle$ $D_{n$에 따라 $회로{\displaystyle {}_{}}$ ${\displaystyle {Dn}_{}}${\$displaystyle$$d_{n$}이 존재하므로 L을 정의하는 공식은 다음과 같다$.$

${\displaystyle \forall x.\phi(x,D_{n}(x,z),z)}$

(1)

더욱이 회로는 실존적 계량화로 추측할 수 있다.

$\displaystyle \exists D.\forall x.\phi(x,D(x,z),z)}$

(2)

분명히 (1)은 (2)를 암시한다.(1)이 거짓이면 then${\displaystyle \mathrm{}y}$ y .${\displaystyle \varphi }$ (${\displaystyle }$x${\displaystyle }$, ${\displaystyle y}$, ${\displaystyle z}$) ${\displaystyle \neg \exists$ y$.$$\phi(x,y,z$ 이 경우 어떤 회로 D도 $\varphi {\displaystyle (x,}$ ${\displaystyle D(x,}$ z$){\$ true를$$ 만드는 할당을 출력할 수 없다.

증거에$$ 따르면 $\pi {\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$\Pi $_{2$}}$세트{\displaystyle }$L {\$displaystyle$ L$$$}$이(${\displaystyle {가\mathrm{}}_{}}$) $\$ 2 {\$displaystyle$ \$Sigma _{2$

더욱이 $\pi {\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$공식은$$ 사실이라면 회로 D는 x에 대해 작동한다. $\pi {\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$2$$$}}$ 공식은 거짓이면, x를 만드는 공식이 어떤 회로에도 작용한다.이 속성은 S 복잡도^P
₂ 등급(즉, ${\displaystyle {\pi \mathrm{}}_{}}$ 2 ${\displaystyle {}_{}}$ ${\displaystyle {\mathsf{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle P_{\mathrm{}}^{}}$ ${\displaystyle {}_{}^{}}$ ⊆ 2 ${\displaystyle {2\mathrm{}}_{}}$ $\$ \ 2 {\$displaystyle$ \$Pi _${2}\$subseteq${\$mathsf{S}}^{P}}}\subseteq \subseteq$\sigma _${2}})$에 대해 더 강한 붕괴를 의미한다.$$그것은 Sengupta에 의해 관찰되었다.^[2]

AM = MA

위의 증빙을 수정하면^[3] 결과가 나온다.

${\displaystyle {\mathsf {NP}\subseteq {\mathsf {P/poly}\implies {\mathsf {AM}={\mathsf {MA}}}}$

(Arthur-Merlin 프로토콜 참조).

L이 AM에 있다고 가정합시다.

$\displaystyle z\in L\implies \Pr \nolimits _{x}[exists y.\phi(x,y,z)]\geq {\tfrac {2}{3}}$

$\displaystyle z\notin L\implies \Pr \nolimits _{x}[exists y.\phi(x,y,z)]\leq {\tfrac {1}{3}}$

그리고 이전에 $\exists {\displaystyle \mathrm{}}$ ${\displaystyle y}$ .${\displaystyle \varphi }$( ${\displaystyle x}$, ${\displaystyle y}$, z${\displaystyle }$)$${\$displaystyle \exists y.$$다음$과$$같은 경우 만족스러운 할당을 $출력$하는 ${\displaystyle {회로}_{}}$ Dn {\$displaystyle D_{n}$을(를) $사용하여 \phi(x$,$y,z$)}:

${\displaystyle z\in L\implies \Pr \nolimits _{x}[\x_{n}(x,z),z)]\geq {\tfrac {2}{3}}}}$

${\displaystyle z\notin L\implies \Pr \nolimits _{x}[\x_{n}(x,z),z)]\leq {\tfrac {1}{1}{3}}}}}$

${\displaystyle {Dn}_{}}$ ${\$은(는) 다음과 같이 추측할$$ 수 있다.

$L\implies \exist D.\Pr \nolimits _{x}[\phi (x,D(x,z),z)]\geq {\tfrac {2}{3}}}}$

$L\implies \forall D.\Pr \nolimits _{x}[\phi (x,D(x,z),z)]\leq {\tfrac {1}{3}}}$

$L{\displaystyle }$ ${\displaystyle L}$이(가) 더 작은 등급의 MA에 속한다는$$ 것을 증명한다.

회로 하한 적용 – Kannan의 정리

는 SIZE(nk)에 있지 않다 Kannan의 theorem[4]은 고정된 k을 언어를 존재한다는 것 나는{L\displaystyle}Σ에서 2{\displaystyle \Sigma_{2}}, Σ 2보다(이것은 다른 성명 ⊈ P/나는 거예요{\displaystyle \Sigma_{2}\not \subseteq{\mathsf{P/poly}:p}}, 현재와 국가가 열려 있다.주목 ek)에 대해 SIZE(n^k)에 없는 단일 언어를 xists로 표시한다.그것은 단순한 회로 하한이다.

증명 개요:

$L{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle {4\mathrm{}}_{}}$- ${\displaystyle S\mathsf{}}$ ${\displaystyle \mathsf{I}}$ Z ${\displaystyle \mathsf{E}}$ ${\displaystyle ({}^{}}$ ${\displaystyle k^{}}$ ) $displaystyle L\in \Sigma _{4}-{\mathsf$ {$SIZE}}(n^{k})$라는 언어가 있다($$증거는 대각화 기법을 사용한다).다음 두 가지 경우를 고려하십시오.

• If ${\displaystyle {\mathsf {SAT}}\notin {\mathsf {P/poly}}}$ then ${\displaystyle {\mathsf {SAT}}\notin {\mathsf {SIZE}}(n^{k})}$ and theorem is proved.
• If ${\displaystyle {\mathsf {SAT}}\in {\mathsf {P/poly}}}$, then by Karp–Lipton theorem, ${\displaystyle \Sigma _{4}=\Sigma _{2}}$ and therefore ${\displaystyle L\in \Sigma _{2}-{\mathsf {SIZE}}(n^{k})}$.

Karp-Lipton의 더 강한 버전은 Kannan의 정리를 다음과 같이 강화한다: 어떤 k에 대해서도 $L{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle {\mathsf{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle P_{\mathrm{}}^{}}$- S ${\displaystyle \mathsf{I}}$ ${\displaystyle \mathsf{Z}}$ E${\displaystyle }$(${\displaystyle n^{}}$ k${\displaystyle {}^{}}$) ${\displaystyle L\in {\mathsf {S}_{2}^{P}-{\mathsf {SIZ}-{{{SIZ$

$또한{\displaystyle \mathsf{}}$ 비노드찬드란이 입증한 S I ${\displaystyle \mathsf{Z}}$ ${\displaystyle \mathsf{E}}$ ${\displaystyle (n^{}}$ k${\displaystyle {}^{}}$) ${\displaystyle {\mathsf {SIZE}(n^{k})$에 PP가 포함되어 있지 않은 것으로 알려져 있다$.$^[5]증명:^[6]

• If ${\displaystyle {\mathsf {PP}}\not \subseteq {\mathsf {P/poly}}}$ then ${\displaystyle {\mathsf {PP}}\not \subseteq {\mathsf {SIZE}}(n^{k})}$.
• 그렇지 않으면 $P{\displaystyle {\mathsf{}}^{\mathsf{}}}$# ${\displaystyle {\mathsf{P}}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle P\mathsf{}\mathsf{}}$/ ${\displaystyle p\mathsf{}}$ ${\displaystyle \mathsf{o}}$ ${\displaystyle \mathsf{l}}$ ${\$ {$P/poly$ 이후

${\displaystyle {\mathsf{P}}^{\mathsf{}}}$# ${\displaystyle {\mathsf{P}}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle \mathsf{P}}$ ${\displaystyle \supseteq }$ ${\displaystyle \mathsf{M}}$ A ${\$ {$PP}\supseteq {\mathsf {MA}($MA 속성별)$$

${\displaystyle {\mathsf {P^{\#P}}}\supseteq {\mathsf {PH}}\supseteq \Sigma _{2}\supseteq {\mathsf {MA}}}$ (by Toda's theorem and property of MA)

${\displaystyle {\mathsf{P}}^{\mathsf{}}}$# ${\displaystyle {\mathsf{P}}^{}}$= ${\displaystyle M\mathsf{}}$ ${\displaystyle \mathsf{A}}$ ${\$영구성을 위한 대화형 프로토콜을 사용한 가정에서 비롯됨, P/폴리 참조)

함량은 같으며, ${\displaystyle \mathsf{우리}}$는 칸난의 정리대로$$ $P{\displaystyle \mathsf{}}$ =${\displaystyle }$⊈ ${\displaystyle {2\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle S\mathsf{}}$ ${\displaystyle \mathsf{I}}$ ${\displaystyle \mathsf{Z}}$ E ${\displaystyle (n^{}}$ k$){\displaystyle {\mathsf{PP}=\Sigma _{2}\not \subseteq${\$mathsf$ {$SIZE}(n$^{$k})}}$을 얻는다.

참조

• Karp, R. M.; Lipton, R. J. (1980), "Some connections between nonuniform and uniform complexity classes", Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, pp. 302–309, doi:10.1145/800141.804678.

• Karp, R. M.; Lipton, R. J. (1982), "Turing machines that take advice", L'Enseignement Mathématique, 28: 191–209, doi:10.5169/seals-52237.