패리티 함수

부울 대수에서 패리티 함수는 입력 벡터에 홀수 수가 있는 경우에만 값이 1인 부울 함수다. 두 입력의 패리티 함수는 XOR 함수로도 알려져 있다.

패리티 함수는 부울 함수의 회로 복잡성에 대한 이론적 조사에서의 역할로 주목할 만하다.

패리티 함수의 출력은 패리티 비트다.

정의

The ${\displaystyle n}$-variable parity function is the Boolean function ${\displaystyle f:\{0,1\}^{n}\to \{0,1\}}$ with the property that ${\displaystyle f(x)=1}$ if and only if the number of ones in the vector ${\displaystyle x\in \{0,1\}^{n}}$ is odd. 즉, $f{\displaystyle }$ ${\displaystyle f}$은(는) 다음과 같이 정의된다$$.

${\displaystyle f(x)=x_{1}\oplus x_{2}\oplus \oplus \oplus \oplus \oplus x_{n}}}$

여기서 $▼{\displaystyle }$ ${\displaystyle \oplus }$은(는) 또는

특성.

패리티는 패리티의 수에 따라서만 달라지며 따라서 대칭 부울 함수다.

n-변수 패리티 함수와 부정은 모든 이항 정규 형태는 최대 2개의 ^{n − 1} 단항수 n을 가지며 모든 결합 정규 형태는 최대 2개의 ^{n − 1} 항을 가지는 유일한 부울 함수다.^[1]

계산 복잡성

계산 복잡성의 초기 작업 중 일부는 Bella Subbotovskaya의 1961 바인딩으로 부울 공식 계산 패리티의 크기는 적어도 $O{\displaystyle }$ ${\displaystyle ({n\mathrm{}}^{}}$ 3${\displaystyle {}^{}}$/ $){\displaystyle$O$(n^{3/2})$이어야 한다$.$ 이 작업은 무작위 제한의 방법을 사용한다. $3{\displaystyle \mathrm{}}$ / ${\displaystyle 3/2$}의 이 지수는 신중한 분석을 통해 패터슨과 즈윅(1993)이${\displaystyle \mathrm{}}$1.$[\displaystyle$1.$63}$을(를) 한 다음, 호스타드(1998)가 2$[\displaystyle 2}$을(를)로 증가시켰다$$. ^[2]

1980년대 초 메릭 퍼스트, 제임스 색스, 마이클 시퍼와^[3] 독립적으로 미클로스 아제이는^[4] 패리티 기능에 대한 일정한 깊이 부울 회로의 크기에 대한 초다항식 하한을 설정했다. 즉, 다항식 크기 상수심 회로가 패리티 함수를 계산할 수 없다는 것을 보여주었다. 패리티 함수의 감소에 의해 대다수의 곱셈 및 전이성 폐쇄 기능에 대해서도 유사한 결과가 확립되었다.^[3]

Håstad(1987)는 패리티 함수에 대한 일정한 깊이 부울 회로의 크기에 대해 엄격한 지수 하한을 설정했다. 호스타드의 스위칭 레마(Switching Leemma)는 이러한 하한에 사용되는 핵심 기술 도구로, 요한 호스타드는 1994년 이 작품으로 괴델상을 받았다. 정확한 결과는 AND, OR 및 NOT 게이트가 있는 깊이-k 회로는 패리티 함수를 계산하기 위해$$ 크기 ${\displaystyle \exp }$ ${\displaystyle (\mathrm{\Omega }}$(${\displaystyle {}^{}}$ ${\displaystyle {\frac{1}{}}^{}}$ ${\displaystyle {\frac{\mathrm{k}}{}}^{}}$- 1${\displaystyle {\frac{}{}}^{}}$)${\displaystyle \exp(n^{\frac{$1}{$k-1})})$를 필요로 한다는 것이다. 이는 크기 ${\displaystyle \exp }$ ${\displaystyle }$(${\displaystyle {O\frac{\mathrm{}}{}}^{}}$( ${\displaystyle {\frac{1}{}}^{}}$k${\displaystyle {\frac{}{}}^{}}$- ${\displaystyle 1}$ ) t$){\displaystyle \exp(O(n^{\frac{1}{k-1}t$을(를) 가진 깊이-k 회로 계산 패리티가 있기 때문에 무증상적으로 거의 최적이다.

무한 버전

$무한$ 패리티 $함수$는 $함수{\displaystyle }$f${\displaystyle }$:$${ ${\displaystyle 0,}$ ${\displaystyle 1{}^{\Omega }}$ ${\displaystyle {}^{}}$ { ${\displaystyle 0,}$ $}$ {\$displaystyle$f\$colon$\{0,1$\}^{0$,1\}\$omega \}\\to$ $\{$$0,$$1$$\}}}}}}$을(를$)$ 무한$$ 이진 문자열마다 0 또는 1로 매핑하는$$ $속성$이다.$s{\displaystyle }$ ${\displaystyle \mathrm{그러면}}$ w$${\$displaystyle$w$$}과($와{\displaystyle }$)$$v {\$displaystyle$ v$}$이(가) 짝수 좌표 수에 따라 다를$$ 경우에만$$ f${\displaystyle }$( w${\displaystyle }$)${\displaystyle }$= ${\displaystyle f}$(${\displaystyle v}$) ${\displaystyle f(w)=f(v)}.$

Assuming axiom of choice it can be easily proved that parity functions exist and there are ${\displaystyle 2^{\mathfrak {c}}}$ many of them - as many as the number of all functions from ${\displaystyle \{0,1\}^{\omega }}$ to ${\displaystyle \{0,1\}}$. It is enough to take one representative per 관계 $\approx {\displaystyle }$의 동등성 클래스 ${\displaystyle$\$$약$}$은(는) ${\displaystyle \mathrm{다음}}$과 같이 정의됨$$: $w{\displaystyle }$ ${\displaystyle \approx }$ v ${\displaystyle w\$약$v}($$와{\displaystyle }$) w ${\displaystyle$ $w$$}$과 $v{\displaystyle }$ ${\displaystyle$ v$}$이(가) 제한된 좌표 수로 서로 다를$$ 경우$$ 그러한 대표가 있으면 우리는 그들 모두를 0으로 매핑할 수 있고, 나머지 $f{\displaystyle }$ ${\displaystyle f}$ 값은$$ 모호하지 않게 공제된다.

무한 패리티 함수는 종종 이론적인 컴퓨터 과학과 세트 이론에서 종종 사용된다. 그 이유는 단순한 정의와 다른 한편으로는 서술적인 복잡성 때문이다. 예를 들어 역 영상 $f{\displaystyle {}^{}}$- ${\displaystyle 1^{}}$[ ${\displaystyle 0}$ ${\displaystyle ]}$ ${\displaystyle f^{-1}[0]}$이(가) 비보렐 집합임을 나타낼 수 있다.

참고 항목

• 월시함수, 연속 등가함수
• 패리티 비트, 함수의 출력
• 독립적인 투입을 위한 통계적 속성인 쌓기 보조정리
• 다방향 전환, 조명 제어에 자주 사용되는 물리적 구현

관련 항목:

• 오류 수정
• 오류 탐지

참조