다항식 아이덴티티 테스트

수학에서 다항식 아이덴티티(PIT)는 다항식 다항식 두 개가 동일한지 여부를 효율적으로 판단하는 문제다.보다 형식적으로 PIT 알고리즘에는 필드에서 다항식 p를 계산하는 산술 회로가 주어지며, p가 0 다항식인지 여부를 결정한다.다항식 아이덴티티 테스트에 필요한 계산 복잡성을 결정하는 것은 대수적 계산 복잡성에 있어 가장 중요한 개방적 문제 중 하나이다.

설명

"${\displaystyle }$( ${\displaystyle x}$+ y${\displaystyle }$)${\displaystyle }$( ${\displaystyle x}$- ${\displaystyle y}$) ${\displaystyle (x+y)(x-y)}$이(가) $x$ ${\displaystyle {2\mathrm{}}^{}}$ -${\displaystyle {}^{}{y\mathrm{}}^{}}$ 2${\displaystyle {}^{}}$? ${\displaystyle x^{2}-y^{2}\,$ $?\}"$은 두 다항식이 동일한지 여부에 대한 질문이다.다른 다항식 ID 시험 문제와 마찬가지로, "특정 다항식이 0과 동일한가?"라는 질문으로 사소한 변환을 할 수 있다. 이 경우 "(${\displaystyle x}$+ y${\displaystyle }$)${\displaystyle }$(${\displaystyle x}$- ${\displaystyle {y\mathrm{}}^{}}$)${\displaystyle }$-${\displaystyle }$(${\displaystyle {x\mathrm{}}^{}}$2 -${\displaystyle {}^{}y}$) = ${\displaystyle 0}$ ${\displaystyle (x+y)(x-y)-(x^{2$}-$y^{$2}-^{$2}=0}"?$대수적 표현(블랙박스가 아닌)으로서 다항식을 준다면, 우리는 균등이 (${\displaystyle n\genfrac{}{}{0ex}{}{}{}}$+ ${\displaystyle \genfrac{}{}{0ex}{}{}{}}$ ) 과 덧셈을 통해 유지됨을 확인할 수 있지만, brute-force 접근법의 시간 복잡성은 $({\displaystyle }$n + ${\displaystyle \genfrac{}{}{0ex}{}{d}{}}$) ${\$ 스타일 ${\tbinom {n+d}{d$ 여기서 $n{\displaystyle }$ ${\d}$은 n$}$이 된다.변수 움버(여기서, ${\displaystyle \mathrm{n}}$= 2 ${\displaystyle n=2$ : x$${\$displaystyle x}$은 첫 번째, $y{\displaystyle }$ ${\displaystyle$ $y$$}$은$($여기서$,$ ${\displaystyle \mathrm{d}}$= 2 ${\displaystyle d=2})$의 정도.$n{\displaystyle }$ ${\displaystyle n}$과 $d{\displaystyle }$ ${\displaystyle d}$이(가) 모두 크면$({\displaystyle \genfrac{}{}{0ex}{}{}{}}$+ ${\displaystyle \genfrac{}{}{0ex}{}{d}{}}$) ${\$이(가) 기하급수적으로 증가한다$$.^[1]

PIT는 다항식이 구현한 함수가 항상 주어진 영역에서 0으로 평가되는지 보다는 다항식이 0 다항식과 동일한지 여부를 우려한다.예를 들어, 두 요소인 GF(2)가 있는 필드에는 원소 0과 1만 들어 있다.GF(2)에서 $x{\displaystyle {}^{}}$ 2${\displaystyle {}^{}}$- x ${\displaystyle x^{2}-x}$는 항상$$ 0으로 평가되며, 그럼에도 불구하고 PIT는 ${\displaystyle {x\mathrm{}}^{}}$ 2 -${\displaystyle {}^{}x}$ ${\displaystyle x^{2}-x}$을(를) 0 다항식과 동일하게 간주하지 않는다.^[2]

다항식 아이덴티티 테스트에 필요한 계산 복잡성을 결정하는 것은 "알지브레이크 컴퓨팅 복잡성"^[1][3]으로 알려진 수학 하위 분야에서 가장 중요한 개방형 문제 중 하나이다.PIT에 대한 연구는 IP=PSPACE의 증명과 같은 계산 복잡성의 다른 많은 영역에 대한 빌딩 블록이다.^[1][4]또한 PIT는 Tutte 행렬 및 Primality testing에도 적용이 있으며, 여기에서 PIT 기법은 AKS primality test로 이어졌으며, Primality test를 위한 첫 번째 결정론적(비실용적이지만) 다항식 시간 알고리즘이다.^[1]

형식문제명세서

필드에서 다항식을 계산하는 산술 회로에 따라 다항식이 0 다항식(즉, 0이 아닌 항이 없는 다항식)과 동일한지 여부를 결정한다.^[1]

해결 방법

산술 회로의 사양이 PIT 해결사에게 주어지지 않는 경우도 있으며, PIT 해결사는 회로를 구현하는 "블랙박스"에만 값을 입력한 다음 출력을 분석할 수 있다.아래 솔루션은 주어진 필드의 모든 연산(예: 곱셈)이 일정한 시간이 걸린다고 가정하며, 나아가 아래의 모든 블랙박스 알고리즘은 필드의 크기가 다항식의 크기보다 크다고 가정한다.

슈워츠-지펠 알고리즘은 입력을 무작위로 테스트하고 출력이 0인지 확인하는 것만으로 실용적인 확률론적 솔루션을 제공한다.그것은 정확성이 입증된 최초의 무작위화된 다항식 시간 PIT 알고리즘이었다.^[1]입력 내용이 더 큰 도메인에서 도출될수록 슈워츠-지펠이 실패할 가능성이 더 낮다.랜덤 비트가 부족한 경우, Chen-Kao 알고리즘(합리성 위에) 또는 Lewin-Vadhan 알고리즘(모든 필드에 걸쳐)은 더 많은 필요한 런타임의 비용으로 더 적은 수의 랜덤 비트를 요구한다.^[2]

희박한 PIT에는 최대 $m{\displaystyle }$ ${\displaystyle m}$의 0이 아닌 단일 항이 있다.희소성 PIT는 회로 $크기$와 숫자 m의 다항 $시간$에서 결정적으로 해결될 수 있다$($^[1]또한 $참조).$^[5]

낮은 도 PIT는 다항식의 도에 상한을 가진다.저도 PIT 문제는 심도 4 회로에 대한 PIT 문제에 대한 회로 크기의 하위 시간 내에 줄일 수 있으므로 심도 4 회로(이하)의 회로에 대한 PIT를 집중적으로 연구한다.^[1]

참고 항목

• 슈워츠-지펠 보조정리 적용사례

외부 링크

• "슈워츠-지펠 보조기구의 폴리노믹 아이덴티티 테스트"에 대한 강의 노트
• Michael Forbes의 다항식 ID 테스트 - 유튜브에서 MIT on YouTube
• 다항식 Identity Testing 수상자

참조