AC0 함수의 공식 크기 하한 o (

의문:

AC ⁰ 의 명시 적 함수에 대해 가장 잘 알려진 공식 크기 하한은 무엇입니까 ? 하한이 인 명시 적 기능이 있습니까? $Ω (n^{2})$
Ω(n2)

배경:

대부분의 하한과 마찬가지로 수식 크기의 하한은 구하기 어렵습니다. 표준 범용 게이트 세트 {AND, OR, NOT}에 대한 공식 크기 하한에 관심이 있습니다.

이 게이트 세트에서 명시 적 함수에 대해 가장 잘 알려진 공식 크기 하한은 Andreev에 의해 정의 된 함수에 대해 입니다. 이 범위는 Håstad에 의해 보여졌으며 Andreev의 의 하한을 개선했습니다 . 또 다른 명시적인 하한 은 패리티 함수에 대한 Khrapchenko의 하한입니다. $Ω (n^{3 - o (1)})$

Ω(n3−o(1))

$Ω (n^{2.5 - o (1)})$

Ω(n2.5−o(1))

$Ω (n^{2})$

Ω(n2)

그러나이 두 기능은 AC ^0에 없습니다 . AC ⁰ 에서 2 차 (또는 더 나은) 하한을 갖는 명시 적 함수를 알고 있는지 궁금합니다 . 내가 알고있는 최선의 경계는 Nechiporuk가 보여주는 것처럼 요소 구별 기능에 대한 하한입니다. 요소 구별 기능은 AC ⁰ 에 있으므로 보다 나은 명시 적 AC ⁰ 기능 , 바람직하게는 에 대한 하한을 찾고 있습니다. $Ω (n^{2} / \log n)$

Ω(n2/log⁡n)

$Ω (n^{2} / \log n)$

Ω(n2/log⁡n)

$Ω (n^{2})$

Ω(n2)

더 읽을 거리 :

이 주제에 대한 훌륭한 자료는 Stasys Jukna의 “Boolean Function Complexity : Advances and Frontiers”입니다. 책 초안은 그의 웹 사이트에서 무료로 구할 수 있습니다.

답변

좋은 질문입니다! Khrapchenko는 함수에 대해 2 차 하한을 제공 할 수 없습니다 . 그의 하한은 사실 적어도 평균 감도의 제곱입니다. 모든 함수 는 다 로그 평균 감도를 갖습니다. Subbotovskaya-Andreev는 또한 그들이 사용하는 주장 (임의 제한으로 인해 훨씬 더 작은 공식이 발생 함)이 큰 회로 크기를 강요하는 이유이기 때문에 그러한 기능을 제공 할 수 없습니다 . Hastad ‘s Switching Lemma (잘 모르겠 음, 직관). 유일한 희망은 Nechiporuk입니다. 그러나 그의 주장은 이상을 줄 수 없다 $A C^{0}$

AC0

$A C^{0}$

AC0

$A C^{0}$

AC0

$n^{2} / \log n$

n2/log⁡n

정보 이론적 이유에 의해. 그렇다면 모든 것이 2 차 (또는 더 작은) 크기의 공식을 가질 수 있습니까? 나는 그것을 믿지 않지만 빨리 반례를 찾을 수 없었습니다. $A C^{0}$

AC0

$2 n$

$n \times n$

n×n

$G$

$V = {1, \dots, 2 n}$

V={1,…,2n}

$a$

$i$

$j$

$i \leq n$

i≤n

$j > n$

j>n

$a$

$i$

$j$

$G$

$n^{ϵ}$

nϵ

$Σ_{3}$

Σ3

$n^{1 / 2}$

n1/2

$2 m = 2 \log n$

2m=2log⁡n

$n^{ϵ}$

nϵ

답변

증거 복잡성에 대한 장을보고자하는 Kaveh에게 감사합니다!

$A C^{0}$

AC0

$n^{k}$

$k$

$A C^{0}$

AC0

$A C^{0}$

AC0

$\exp (n^{k})$

exp⁡(nk)

$k$

$\exp (t \log n)$

exp⁡(tlog⁡n)

$t$

$n^{2}$

$n$

$F (X) = f (g (X_{1}), \dots, g (X_{b}))$

F(X)=f(g(X1),…,g(Xb))

$b = \log n$

b=log⁡n

$g$

$A C^{0}$

AC0

$n / b$

n/b

$f$

$b$

$f$

$g$

$k$

$X$

$g$

$2$

$3 / 2$

3/2

$F (X)$

F(X)

$n^{3} / k^{2}$

n3/k2

$A C^{0}$

AC0

$n^{1 / d}$

n1/d

$d \geq 2$

d≥2

$n^{2}$

$A C^{0}$

AC0

$n^{1 / 2}$

n1/2

변수. 그러한 기능을 2보다 큰 깊이로 검색해야합니다.

$F (X)$

F(X)

$n^{2} / \log n$

n2/log⁡n

$n / b$

n/b

$F (X)$

F(X)

$s$

$X_{i}$

$g (X_{i})$

g(Xi)

$n / b$

n/b

$s$

$n / b = n / \log n$

n/b=n/log⁡n

$2^{b} / \log b = n / \log \log n$

2b/log⁡b=n/log⁡log⁡n

$f$

$s \geq n^{2 - o (1)}$

s≥n2−o(1)

$n^{2}$

$(d + 1)$

(d+1)

$d$

How IT

언제든지 물어보세요.

AC0 함수의 공식 크기 하한 o (

답변

답변

답변