산술 회로 복잡도

계산 복잡성 이론에서 산술 회로는 다항식 계산의 표준 모델이다.비공식적으로, 산술 회로는 변수나 숫자 중 하나를 입력으로 사용하고, 이미 계산한 두 개의 식을 추가하거나 곱할 수 있다.산술 회로는 다항식 계산의 복잡성을 이해하는 공식적인 방법을 제공한다.이 연구 라인의 기본적인 질문 유형은 "주어진 다항식 $f{\displaystyle }$ ${\displaystyle$ f$}$을(를) 계산하는 가장 효율적인 방법은 무엇인가?"$$이다.

정의들

필드 $F{\displaystyle }$ ${\displaystyle F}$ 및 변수$$ x ${\displaystyle {1\mathrm{}}_{}}$, ${\displaystyle \dots ,}$ ${\displaystyle x_{}}$ n ${\$의 산술 회로 $C{\displaystyle }$ ${\displaystyle C}$는 다음과 같은 방향의 AC 순환 그래프입니다.외설적인 0이 있는 그것의 모든 노드를 $입력{\displaystyle {}_{}}$ ${\displaystyle {게이트}_{}}$라고 하며 변수 x i ${\$ 또는$$ $F{\displaystyle .}$ ${\displaystyle F.}$의 필드 요소에 의해 레이블이 지정된다. 다른 모든$$ 게이트는 첫 번째 경우$$${\displaystyle }$+ ${\displaystyle +}$ 또는$$${\displaystyle }$×; ${\displaystystyle \times;}$로 레이블이 지정되며 두 번째 p.회전 관문산술 공식은 모든 게이트가 1도 밖에 없는 회로(따라서 기본 그래프는 지시된 트리)이다.

회로에는 크기와 깊이라는 두 가지 복잡성 측도가 연관되어 있다.회로의 크기는 그 안에 있는 관문의 수이고, 회로의 깊이는 그 안에서 가장 긴 방향의 경로의 길이다.예를 들어 그림의 회로는 크기 6과 깊이 2가 있다.

산술 회로는 다항식을 다음과 같은 자연적인 방법으로 계산한다.입력 게이트는 라벨이 부착된 다항식을 계산한다.Sum $gate{\displaystyle }$v {\$displaystyle$ v$}$은(는$)$ 하위 항목이 계산한 다항식의 합계를$$ 계산한다(${\displaystyle \mathrm{directed}\mathrm{edge}(}$v$$, u ) {\$displaystyle$ v}이$($가) 그래프에 있는$$ 경우$$$$v {\$displaystyle$ v$}$의 하위 항목임$$).제품 게이트는 자녀가 계산한 다항식의 곱을 계산한다.Consider the circuit in the figure, for example: the input gates compute (from left to right) ${\displaystyle x_{1},x_{2}}$ and ${\displaystyle 1,}$ the sum gates compute ${\displaystyle x_{1}+x_{2}}$ and ${\displaystyle x_{2}+1,}$ and the product gate computes ${\displaystyle (x_{}}$${\displaystyle (x_{1}+x_{2}x_{$$2}}(x_{2}+1$$}$

개요

다항식 $f{\displaystyle ,}$ ${\displaystyle f,}$을(를) 고려할 때, 우리는$$ 그것을 계산하는 가장 좋은 방법이 무엇인지 자문할 수 있다. 예를 들어, 회로 계산 $f$의 가장 작은 크기는 무엇인가${\displaystyle .}$ ${\displaystyle f.}$ 이 질문에 대한$$ 답은 두 부분으로 구성되어 있다.첫 번째 부분은 $f{\displaystyle ;}$ ${\displaystyle$ $f$$;}$을(를) 계산하는 회로를 찾는 것이다. 이 부분을$$ 보통 $f$의 복잡성 상한이라고 한다${\displaystyle .}$ ${\displaystyle$ f$.}$다른$$ 회로는 더 잘 할 수 없다는 것을 보여준다. 이 부분은 f${\displaystyle .}$ ${\displaystyle$ f$.}$의 복잡성 하한 경계라고 한다. 이 두 가지 작업에도$$ 불구하고하한을 증명하려면 모든 회로에 대해 동시에 논쟁해야 하기 때문에 하한을 증명하는 것은 일반적으로 더 어렵다.

다항식이 정의하는 함수보다는 다항식의 공식 계산에 관심이 있다는 점에 유의하십시오.예를 들어, 이 다항식이 영 함수를 나타내지만 영 다항식이 아닌 두 요소의 필드 위에$$ 있는 $다항식{\displaystyle {}^{}}$ x${\displaystyle {}^{}2}$ + x${\displaystyle ;}$ ${\displaystyle x^{2$}+$x;}$을(를) 고려하십시오.이것은 산술 회로 연구와 부울 회로 연구의 차이점 중 하나이다.부울 복잡성에서는 함수의 일부 표현보다는 함수의 계산에 주로 관심이 있다(우리의 경우 다항식 표현).이것이 부울 복잡성을 산술적 복잡성보다 더 어렵게 만드는 이유 중 하나이다.산술 회로에 대한 연구도 우리가 거의 이해하지 못하는 부울 케이스의 연구를 향한 중간 단계의 하나로 간주될 수 있다.^[1]

상한

다항식 계산의 복잡성에 대한 연구의 일환으로, 몇몇 영리한 회로(대안 알고리즘)가 발견되었다.잘 알려진 예는 매트릭스 제품에 대한 Strassen의 알고리즘이다.두 ${\displaystyle 개}$의 n ${\displaystyle \times }$ n ${\displaystyle$ n$\times n}$매트릭스의$$ 제품을 계산하는 간단한 방법은 크기 순서 $n{\displaystyle {}^{}}$ ${\displaystyle 3^{}}$의 회로를 필요로 한다${\displaystyle {}^{}}$ ${\displaystyle$ n$^{3}}}}$Strassen은$$ 사실 $대략{\displaystyle {}^{}}$ ${\displaystyle {2.807}^{}}$ ${\displaystyn^{2.807}}}}}$Strassen의$$ 기본 아이디어는 것을 보여주었다.2에 2를 2로 곱하기 위해 지렛대 역할을 한다.이 아이디어는 대략 $n{\displaystyle {}^{}}$ ${\displaystyle {2.376}^{}}$ ${\displaystyle$ n$^{2.376}$ 시간이 걸리는 두 행렬을 곱하기 위한 최선의 이론적 방법의 출발점이다.

또 다른 흥미로운 이야기는 $n{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle n}$ ${\displaystyle n\times n}$ 행렬의$$ 결정인자 계산 뒤에 있다.결정인자를 계산하는 순진한 방법은 대략 $n{\displaystyle !}$ .${\displaystyle n!$의 회로가 필요하다.$}$ {\$displaystyle n}$에는 결정인자를 계산하기 위한$$ 크기의 다항식 회로가 있다는 것을 알고 있다.그러나 이러한 회로는 $n{\displaystyle .}$ ${\displaystyle$ n$.}$에서 선형인 깊이를 가지고 있다. 버코위츠는$$ $n{\displaystyle ,}$ ${\displaystyle$ n$,}$의 크기 다항식 회로이지만 깊이 $O{\displaystyle (\log }$ 2${\displaystyle {2\mathrm{}}^{}}$ ( n${\displaystyle ).}$ ${\displaysty O(\log ^{2}(n$)))의 회로가 개선되었다$.$$}$^[2]

우리는 $또한{\displaystyle }$ n ${\displaystyle \times }$ ${\displaystyle n}${\$displaystyle$ n$\time n$} 행렬의 영구성으로 알려진 최고의 회로를 언급하고 싶다.결정인자에 대해서는, 영구적인 것을 위한 순진한 회로의 크기는 대략 $n{\displaystyle !}$. ${\displaystyle n!$$}}$ 그러나$$ 영구적인 경우 알려진 최고 회로의 크기는 대략 ${\displaystyle \mathrm{2n}}$ ,${\displaystyle 2^{n}}$이며, 이는$$ Ryser의 공식에 의해 주어진다: $n{\displaystyle }$ ${\displaystyle \times }$ n ${\displaystyle n\times$ $n{\displaystyle }$$}$ 행렬$$ X${\displaystyle }$=${\displaystyle }$( ${\displaystyle x_{}}$ i${\displaystyle {}_{}}$,${\displaystyle {}_{}{j}_{}}$) ,$${\$displaystyle$ X$=(x_{i,j}),}),}),}),}}}}}}}}}}}}}$

${\displaystyle \operatorname {perm}(X)=(-1)^{n}\sum _{S\subseteq \{1,\ldots,n\}(1)^{{i=1^{n}\sum_{j\in S}x_{i,j}}}}$

(심도 3회로 입니다.)

하한

하한선 증명이라는 측면에서 우리의 지식은 매우 제한적이다.공식 다항식의 연산을 연구하기 때문에, 우리는 매우 큰 수준의 다항식은 큰 회로를 필요로 한다는 것을 알고 있다. 예를 들어, 도 $2{\displaystyle {\mathrm{}}^{}}$ $[\$의 다항식은 대략 ${\displaystyle {2n}^{}}$ {\$displaystyle$2^{$n}}$ 크기의 회로를 필요로$$ 한다$.$$}$ {\$displaystyle n$ 따라서$$ 주요 목표는 $소수{\displaystyle }$ 다항식의 하한을 n. ${\$displaystyle n$.}$사실$$ 수학의 많은 영역에서처럼 카운트 논거는 초다항식의 회로를 필요로 하는 다항식의 다항식이 있다는 것을 말해준다.그러나 이러한 계산 주장은 대개 계산에 대한 우리의 이해를 향상시키지 못한다.다음의 문제는 이 연구 영역의 주요한 개방적인 문제들이다: 초다항식 크기의 회로를 필요로 하는 다항식의 명시적인 다항식을 찾아라.

The state of the art is a ${\displaystyle \Omega (n\log d)}$ lower bound for the size of a circuit computing, e.g., the polynomial ${\displaystyle x_{1}^{d}+\cdots +x_{n}^{d}}$ given by Strassen and by Baur and Strassen.More precisely, Strassen used Bézout's lemma to show that any circuit that simultaneously computes the ${\displaystyle n}$ polynomials ${\displaystyle x_{1}^{d},\ldots ,x_{n}^{d}}$ is of size ${\displaystyle \Omega (n\log d),}$ and later Baur and Strassen showed the following: giv다항식 $f{\displaystyle }$, ${\displaystyle$ $f$$,}$을(를$)$ 계산하는 $크기$의$$산술 회로에 f . ${\$$displaystyle$ f$}$과($와{\displaystyle )}$ f . {\$displaystyle$ f.}의$$모든 n {\displaystyle$$ n$$$}$ 부분파생물을 계산하는$$ $최대{\displaystyle }$ O${\displaystyle }$($s)$ {\$displaystystystystystylease$.ial derivatives of ${\displaystyle x_{1}^{d}+\cdots +x_{n}^{d}}$ are ${\displaystyle dx_{1}^{d-1},\ldots ,dx_{n}^{d-1},}$ the lower bound of Strassen applies to ${\displaystyle x_{1}^{d}+\cdots +x_{n}^{d}}$ as well.이것은 어떤 상한이 하한을 입증하는 데 도움이 되는 하나의 예다; 바우르와 스트라센에 의해 주어진 회로의 건설은 더 일반적인 다항식들에 대한 하한을 암시한다.

하한을 증명할 수 있는 능력의 부족은 우리에게 계산의 단순한 모델을 고려하게 한다.일부 예로는 모노톤 회로(모든 필드 요소가 음수가 아닌 실제 숫자인 경우), 일정한 깊이 회로 및 멀티라인 회로(모든 게이트가 다항식 다항식을 계산하는 경우)가 있다.이러한 제한된 모델들은 광범위하게 연구되어 왔고 약간의 이해와 결과를 얻었다.

대수 P와 NP

계산 복잡성 이론에서 가장 흥미로운 개방형 문제는 P 대 NP 문제다.대략적으로 이 문제는 주어진 문제에 대한 해결책이 존재한다는 것을 보여줄 수 있는 만큼 쉽게 풀 수 있는지를 판단하는 것이다.그의 정석적인 연구에서 발리안트는^[3] 이 문제의 대수학적 유사점인 VP 대 VNP 문제를 제안했다.

The class VP is the algebraic analog of P; it is the class of polynomials ${\displaystyle f}$ of polynomial degree that have polynomial size circuits over a fixed field ${\displaystyle K.}$ The class VNP is the analog of NP. VNP can be thought of as the class of polynomials ${\displaystyle f}$ of polynomial degree such th단항일 경우 다항식 크기 회로를 사용하여 효율적으로$$ $f{\displaystyle }$ ${\displaystyle$ f$}$의 계수를 결정할 수 있다.

복잡성 이론의 기본 개념 중 하나는 완전성의 개념이다.다항식(예: VP 또는 VNP) 클래스의 경우 이 클래스에 대해$$ 완전한 다항식 f ${\displaystyle$ f$}$이(가) 두 가지 속성을 가진 $다항식$입니다. (1) 클래스의 일부인 경우와 (2) $클래스$에 $있는$ 다른 다항식 $g{\displaystyle }$ ${\$$displaystyle g$$}$이(가) f${\displaystyle }$, ${\stytype f}$보다 쉬운 경우그러면 작은 회로 $g{\displaystyle .}$ ${\displaystyle$ g$.}$ Valiant는$$ 클래스 VNP를 위해 영구적인 것이 완성되었다는 것을 보여주었다.그러므로 VP가 VNP와 같지 않다는 것을 보여주기 위해서는 영구적인 다항식 크기 회로가 없다는 것을 보여줄 필요가 있다.이것은 아직 해결되지 않은 미해결 문제로 남아 있다.

깊이감소

다항식 연산에 대한 우리의 이해에서 한 가지 벤치마크는 발리안트, 스카이움, 버코위츠, 라코프의 작품이다.^[4]그들은 도 $r{\displaystyle }$ ${\displaystyle r}$의 $다항식{\displaystyle }$ f ${\displaystyle f$$}$이(가) $s{\displaystyle ,}$ ${\$$displaystyle$ $s$$}$의 회로 크기가 $s$인 경우$,$ f {\$displaystyle$ f} 및 $깊이$ $O$의 $회로{\displaystyle }$$$${\displaystyle (\log r}$(${\displaystyle r}$) . ${\displaystystylease$ s$}$도 $회로$가 있다는 것을 보여주었다${\displaystyle .}$$(\log(r)\log(s).}$ 예를$$ 들어, 다항식 크기 회로가 있는 $모든$ 다항식 n$${\$displaystyle n}$은(는) 대략 ${\displaystyle {로그\mathrm{}}^{}}$ 2${\displaystyle ㎛(n}$ ${\displaystyle )}$. ${\displaystyle \log ^{2}(n$)의 다항식 크기 회로도 있다$.$$}$ 이 결과는$$ 다항식 크기 회로(결정인자 등)가 있는 모든 다항식 도에 버코위츠의 회로를 일반화한다.부울 설정에서 이 결과의 아날로그는 거짓으로 간주된다.

이 결과의 한 가지 요인은 비교적 작은 공식, quasipolyomal 크기의 공식에 의한 회로 시뮬레이션이다: 도 $r{\displaystyle }$ ${\displaystyle$ r}의$$ $다항식{\displaystyle }$ f ${\displaystyle$ f}이$($가$$$)$ $s{\displaystyle }$,${\$$displaystystyle$ s$,}$의 회로가 있는 경우$$, 크기 O$($ ${\displaystyle {}^{}}$ ${\displaystyle {(r}^{}}$ ${\displaystyle {).}^{}}$${\r)의$공식을 갖는다.$}}$ 이 시뮬레이션은$$ 발리안트 엘알의 깊이 감소보다 쉬우며, 일찍이 히아필이 보여주었다.^[5]

참고 항목

• 다항식 평가의 복잡성에 대한 보다 일반적이고 덜 공식적인 논의를 위한 다항식 평가.

추가 읽기

• Bürgisser, Peter (2000). Completeness and reduction in algebraic complexity theory. Algorithms and Computation in Mathematics. Vol. 7. Berlin: Springer-Verlag. ISBN 978-3-540-66752-0. Zbl 0948.68082.
• Bürgisser, Peter; Clausen, Michael; Shokrollahi, M. Amin (1997). Algebraic complexity theory. Grundlehren der Mathematischen Wissenschaften. Vol. 315. With the collaboration of Thomas Lickteig. Berlin: Springer-Verlag. ISBN 978-3-540-60582-9. Zbl 1087.68568.
• von zur Gathen, Joachim (1988). "Algebraic complexity theory". Annual Review of Computer Science. 3: 317–347. doi:10.1146/annurev.cs.03.060188.001533.

각주