기초 대칭 다항식의 모노톤 산술 회로의 복잡성? st 경로의 합입니다). 이미 40 년

$k$

k

$k$ 번째 기본 대칭 다항식 $S_{k}^{n} (x_{1}, \dots, x_{n})$

S_{k}^{n} (x_{1}, \dots, x_{n})

$S_k^n(x_1,\ldots,x_n)$ 모두의 합 의 제품 구별 변수. 이 다항식 의 모노톤 산술 회로 복잡성에 관심이 있습니다. 간단한 동적 프로그래밍 알고리즘 (아래 그림 1)은 게이트 가있는 회로를 제공합니다 . $(\binom{n}{k})$

(\binom{n}{k})

$\binom{n}{k}$ $k$

k

$k$ $(+, \times)$

(+, \times)

$(+,\times)$ $(+, \times)$

(+, \times)

$(+,\times)$ $O (k n)$

O (k n)

$O(kn)$

질문 :
하한이 알려져 있습니까?
$Ω (k n)$
$Ω (k n)$
$\Omega(kn)$

회로는 스큐 각 제품 게이트의 두 입력들 중 적어도 하나가 가변 인 경우. 이러한 회로는 실제로 스위칭 및 정류 네트워크와 동일합니다 (변수로 레이블이 지정된 일부 모서리가있는 방향성 비순환 그래프. 각 st 경로는 해당 레이블의 곱을 제공하며 출력은 모든 st 경로의 합입니다). 이미 40 년 전에 Markov는 놀라 울 정도로 엄격한 결과를 입증했습니다. 의 최소 모노톤 산술 스큐 회로 에는 정확히 제품 게이트가 있습니다. 상부 경계는도 1을 따른다. :
$(+, \times)$

(+, \times)

$(+,\times)$ $S_{k}^{n}$

S_{k}^{n}

$S_k^n$ $k (n - k + 1)$

k (n - k + 1)

$k(n-k+1)$

그러나 비 왜곡 회로에 대한 그러한 하한을 증명하려는 시도는 보지 못했습니다. 이것이 우리의 “오만”인가, 아니면 그 과정에서 내재 된 어려움이 있습니까?

추신 : 나는 모든 을 동시에 계산하려면 게이트가 필요 하다는 것을 알고 있습니다. 이것은 0-1 입력을 분류하는 모노톤 부울 회로의 크기에 대한 하한선에 따릅니다. Ingo Wegener의 158 페이지를 참조하십시오 . AKS 정렬 네트워크는 또한 암시 게이트이 (부울) 경우에 충분하다. 사실, Baur와 Strassen 은 대한 비 모노톤 산술 회로 의 크기에 대해 밀접한 을 증명했습니다 . 그러나 모노톤 산술 회로는 어떻습니까? $Ω (n \log n)$

Ω (n \log n)

$\Omega(n\log n)$ $S_{1}^{n}, \dots, S_{n}^{n}$

S_{1}^{n}, \dots, S_{n}^{n}

$S_1^n,\ldots,S_n^n$ $O (n \log n)$

O (n \log n)

$O(n\log n)$ $Θ (n \log n)$

Θ (n \log n)

$\Theta(n\log n)$ $S_{n / 2}^{n}$

S_{n / 2}^{n}

$S_{n/2}^n$

답변

하나의 문제는 당신이 “모노톤”제한을 제거하는 경우, 우리는 것입니다 않습니다 효율적으로 그런 일을 계산하는 방법을 알고있다. FFT 기반 다항식 곱셈을 사용하여 시간 으로 모든 (모든 기본 대칭 다항식 평가) 의 값을 계산할 수 있습니다 . 따라서 모노톤 회로 모델에서 하한을 증명하려면 다항식 곱셈에 하한을 증명해야합니다 . $S_{0}^{n}, \dots, S_{n}^{n}$

S_{0}^{n}, \dots, S_{n}^{n}

$S_0^n,\dots,S_n^n$ $n + 1$

n + 1

$n+1$ $O (n \log^{2} n)$

O (n \log^{2} n)

$O(n \log^2 n)$ $Ω (n k)$

Ω (n k)

$\Omega(nk)$ $Ω (n^{2})$

Ω (n^{2})

$\Omega(n^2)$

방법은 다음과 같습니다. 공식적인 미지수 소개 하고 다항식을 고려하십시오 $y$

y

$y$

P (y) = \prod_{i = 1}^{n} (1 + x_{i} y) .

$P(y) = \prod_{i=1}^n (1 + x_i y).$

노트는 이후 것을 의 알려진 상수이며, 이것은 미지와 변량 다항식 및 정도 . 지금 당신은 계수주의 할 에서 정확히 모든 평가하기 때문에, , 그것은 계산하기에 충분 . $x_{i}$

x_{i}

$x_i$ $y$

y

$y$ $n$

n

$n$ $y^{k}$

y^{k}

$y^k$ $P (y)$

P (y)

$P(y)$ $S_{k}^{n}$

S_{k}^{n}

$S_k^n$ $S_{0}^{n}, \dots, S_{n}^{n}$

S_{0}^{n}, \dots, S_{n}^{n}

$S_0^n,\dots,S_n^n$ $P (y)$

P (y)

$P(y)$

이로써 계산하게 에서의 과 다항식의 균형 잡힌 바이너리 트리를 구축 시간 : 잎에서 s ‘를하고 번성 다항식. 도 두 다항식 곱 소요 우리가 재발 얻을 수 있도록, FFT 기술을 사용하여 시간 , 어느로 해결할 입니다. 편의상 요소를 무시하고 있습니다. $P (y)$

P (y)

$P(y)$ $O (n \lg^{2} n)$

O (n \lg^{2} n)

$O(n \lg^2 n)$ $(1 + x_{i} y)$

(1 + x_{i} y)

$(1+x_i y)$ $d$

d

$d$ $O (d \lg d)$

O (d \lg d)

$O(d \lg d)$ $T (n) = 2 T (n / 2) + O (n \lg n)$

T (n) = 2 T (n / 2) + O (n \lg n)

$T(n) = 2 T(n/2) + O(n \lg n)$ $T (n) = O (n \lg^{2} n)$

T (n) = O (n \lg^{2} n)

$T(n) = O(n \lg^2 n)$ $poly (\lg \lg n)$

poly (\lg \lg n)

$\text{poly}(\lg \lg n)$

당신이 사건에 대해 걱정하는 경우 아주 작은, 당신은 계산할 수 에서 만 걱정하는 것을 염두에두고, 비슷한 트릭을 사용하여 시간 (즉, 모든 조건을 버리고 또는 높은 전력 ). $k$

k

$k$ $S_{0}^{n}, \dots, S_{k}^{n}$

S_{0}^{n}, \dots, S_{k}^{n}

$S_0^n,\dots,S_k^n$ $O (n \lg^{2} k)$

O (n \lg^{2} k)

$O(n \lg^2 k)$ $P (x) mod y^{k + 1}$

P (x) mod y^{k + 1}

$P(x) \bmod y^{k+1}$ $y^{k + 1}$

y^{k + 1}

$y^{k+1}$ $y$

y

$y$

물론 FFT는 빼기를 사용하므로 순전히 모노톤 회로에서는 표현할 수 없습니다. 다항식에 모노톤 산술 회로를 효율적으로 곱하는 다른 방법이 있는지 모르겠지만, 다항식 곱셈을위한 효율적인 모노톤 방법은 즉시 문제의 알고리즘으로 이어집니다. 따라서 문제의 하한에는 다항식 곱셈의 하한이 필요합니다.

How IT

언제든지 물어보세요.

기초 대칭 다항식의 모노톤 산술 회로의 복잡성? st 경로의 합입니다). 이미 40 년

답변

답변