전환 보조정리

계산 복잡성 이론에서, Håstad의 스위칭 보조기구는 일정한 깊이의 부울 회로의 크기에 대한 하한을 증명하는 핵심 도구다.요한 호스타드(1987)는 스위칭 보조기를 사용하여 AND, OR, NOT 논리 게이트만 허용되는 깊이 k의 부울 회로에 크기가 필요하다는 것을 보여주었다.

${\displaystyle \exp \left(\Oomega \left)(n^{\frac {1}{k-1}\오른쪽)}$

패리티 함수 계산용.

스위칭 보조정리기는 일부 변수가 무작위로 설정된 깊이-2 회로는 제한 후 극소수의 변수에 대해서만 높은 확률로 의존한다고 말한다.스위칭 보조정리 명칭은 다음과 같은 관찰에서 유래한다.특히 깊이-2 회로인 결합 정상 형태의 임의 공식을 취한다.이제 스위칭 보조정리기는 어떤 변수를 무작위로 설정한 후에, 우리는 몇 개의 변수에만 의존하는 부울 함수를 갖게 된다. 즉, 그것은 어떤 작은 $깊이$의 d$[\displaystyle$ d$}$의 $의사결정$ 트리에 의해 계산될 수 있다$.$이것은 제한된 함수를 이격 정상 형태의 작은 공식으로 쓸 수 있게 해준다.따라서 변수의 무작위 제한에 의해 부딪힌 결합 정상 형태의 공식은 이격 정상 형태의 작은 공식으로 "전환"될 수 있다.

스위칭 보조정리(Håstad 1987년)의 원래 증거는 조건부 확률을 가진 논쟁을 포함한다.거의 틀림없이 더 간단한 증거는 라즈보로프(1993년)와 베임(1994년)에 의해 제시되었다.자세한 내용은 Arora & Barak(2009)의 14장을 참조하십시오.

참조