태그 보관물: circuits

circuits

유사한 입력 배치에서 부울 회로 평가 비트는 플립된다.x∈{0,1}nx∈{0,1}nx \in \{0,1\}^nCCCxxxCCCnnnxxxnnnC(x1),C(x2),…,C(xn)C(x1),C(x2),…,C(xn)C(x^1),C(x^2),\dots,C(x^n)xixix^ixxxiii 를 독립적으로 평가하는

부울 회로가 있다고 가정하십시오.

C

함수를 계산합니다 . 회로가 최대 2 개의 팬인 및 팬 아웃을 갖는 AND, OR 및 NOT 게이트로 구성되어 있다고 가정합니다.

f:{0,1}n→{0,1}

하자 주어진 입력 될. 와 주어지면 단일 비트 위치 에서 와 다른 입력 에 대해 를 평가하고 싶습니다 . 즉, 값 동일하다 그 점을 제외하고 번째 비트는 플립된다.

x∈{0,1}n

C

x

C

n

x

n

C(x1),C(x2),…,C(xn)

xi

x

i

를 독립적으로 평가하는 것보다 더 효율적인 방법이 있습니까?

C

n

에 시간

n

다른 입력?

취하다

C

포함

m

게이트. 그런 다음 독립적으로 평가

C

모두에

n

입력이 필요합니다

O(mn)

시각. 계산하는 방법이 있습니까

C(x1),C(x2),…,C(xn)

o(mn)

시각?


선택적인 맥락 : 우리가 산술 회로를 가지고 있다면 (이 게이트는 곱셈, 덧셈, 부정)

R

그러면 다음을 계산할 수 있습니다.

n

지향성 파생 상품

∂f∂xi(x)

O(m)

시각. 기본적으로 그라디언트 계산을 위해 표준 방법을 사용할 수 있습니다 (역 전파 / 연쇄 규칙).

O(m)

시각. 해당 기능이 연속적이고 차별화 가능하기 때문에 작동합니다. 부울 회로에 대해 비슷한 것을 할 수 있는지 궁금합니다. 부울 회로는 연속적이고 차별화되지 않으므로 동일한 트릭을 수행 할 수는 없지만 사용할 수있는 다른 영리한 기술이 있습니까? 푸리에의 속임수일까요?

(바리안트 질문 : 팬인 및 팬 아웃이 무한한 부울 게이트가있는 경우 평가하는 것보다 점진적으로 더 잘 수행 할 수 있습니까?

C

n

타임스?)



답변

나는 그러한 트릭을 찾기 쉽고 / 또는 사소한 만족도 알고리즘을 제공하기 때문에 상당한 이익을 줄 것 같지 않다고 생각합니다. 방법은 다음과 같습니다.

우선, 표면 상으로는 쉬울지라도, 문제는 실제로 회로의 더 일반적인 문제를 해결할 수 있습니다.

C

N

입력

x0,…,xN−1

평가

C

모든 입력에서보다 빠르게

O~(N⋅|C|)

시각. 그 이유는 우리가 조정할 수 있기 때문입니다

C

회로로

C′

크기의

|C|+O~(Nn)

입력시

0i10N−1−i

, 출력

C(xi)

. 기본적으로, 우리는 단지 작은 조회 테이블을 만듭니다.

0i10N−1−i

xi

그리고 그것을 안으로 연결하십시오

C

.

부울 회로의 배치 평가를위한 사소한 알고리즘을 사용하여 빠른 만족도 알고리즘을 만들 수 있습니다. 다음은 시간에 따라 평가를 수행하는 알고리즘이 있다고 가정하는 간단한 경우의 예입니다.

O~(|C|2−ϵ+(N⋅|C|)1−ϵ/2+N2−ϵ)

어떤 상수에 대해서도

ϵ>0

. 입력 회로

C

확장하여 만족도를 결정할 수 있습니다.

C

회로로

C′

크기의

2n/2⋅|C|

이것은 첫 번째 가능한 모든 선택에 대한 OR입니다.

n/2

에 입력

C

(다른 입력은 무료로 두십시오). 그런 다음 배치 평가

C′

그것의 모든

2n/2

입력. 최종 결과는 다음과 같이 만족스러운 과제를 찾는 것입니다.

C′

iff

C

만족합니다. 러닝 타임은

O~(2(n/2)(2−ϵ)⋅|C|2−ϵ)=O~(2n(1−ϵ/2)⋅poly(|C|))

.


답변