Czy hierarchia upada?

Czy wiemy, że hierarchia się nie zwija ( dla wszystkich )? $\mathsf{TC^0}$ $\mathsf{TC^0_d} \subsetneq \mathsf{TC^0_{d+1}}$ $d$

Wpis do zoo dla $\mathsf{TC^0}$ wspomina tylko o separacji między głębokością 2 i 3.

Czy istnieje również standardowe odniesienie do faktu, że hierarchia $\mathsf{AC^0_d}$ się nie zwija?

cc.complexity-theory reference-request complexity-classes circuit-complexity bounded-depth Kaveh
źródło

Powiązanym pytaniem byłoby, ile różnych funkcji jest dostępnych w

A C_{d}^{0}

$AC_d^0$ /

T C_{d}^{0}

$TC_d^0$ ? Rozsądna dolna granica tych ilości odpowiedziałaby na twoje pytania. Również dowód na ścisłość lematu Hastada może być odpowiedzią na twoje drugie pytanie.

Mahdi Cheraghchi,

W przypadku drugiego pytania, sądzę, że zostało to po raz pierwszy udowodnione w pracy STIP '83 Sipsera „Zestawy Borela i złożoność obwodów” . Daje to jednak tylko super-wielomianowe dolne granice. Pierwsze wykładnicze dolne granice zostały podane przez Yao, później poprawione przez Håstad.

Robin Kothari,

@MCH, czy chciałeś napisać

T C_{d}^{0} / A C_{d}^{0}

$\mathsf{TC^0_d}/\mathsf{AC^0_d}$ ? Czy masz na myśli liczbę klas równoważności problemów w

T C_{d}^{0}

$\mathsf{TC^0_d}$ wrt

A C_{d}^{0}

$\mathsf{AC^0_d}$ ?

Kaveh

Mam na myśli bardzo proste: ile różnych funkcji może reprezentować klasa obwodów o rozmiarze ? (Możemy bardzo łatwo oszacować liczbę obwodów, ale powinniśmy uważać, aby niektóre z nich mogły obliczyć tę samą funkcję.) Gdy pokażesz, że ta liczba rośnie wraz z , to koniec.

A C_{d}^{0}

$AC_d^0$

s

$s$

d

$d$

Mahdi Cheraghchi,

@Dilworth, nonuniform. Liczenie nie wydaje się działać, w przeciwnym razie, jak zauważyłem poniżej, moglibyśmy oddzielić od który jest otwarty.

T C^{0}

$\mathsf{TC^0}$

N C^{1}

$\mathsf{NC^1}$

Kaveh

Odpowiedzi:

Nie znamy dobrych dolnych granic (czyli powiedzmy superminomialnej dolnej granicy dla języka w ) dla obwodów progowych głębokości 2 (ciężary nieograniczone). Obwody o głębokości 3 zbudowane z większości bramek, tj. zawiera tę klasę, dlatego też nie znamy dobrych dolnych granic dla tej klasy. $\mathsf{NEXP}$ $\mathsf{TC}^0_3$

Kristoffer Arnsfelt Hansen
źródło

To odpowiada na moje pytanie. Dziękuję Kristoffer.

Kaveh

Jak napisałem w powyższym komentarzu, nawet jeśli problem w NEXP nie jest znany poza TC , czy nadal nie jest możliwe, że nierównomierna hierarchia TC jest poprawna poprzez dolną granicę argumentu zliczającego?

_{2}^{0}

$^0_2$

^{0}

$^0$

Dilworth

Czy mogę również zapytać, w jaki sposób jest to zgodne ze znanymi wykładniczymi dolnymi granicami TC i oddzieleniem głębokości 3 od obwodów progowych głębokości 2, jak podano w zoo złożoności? Czy coś brakuje?

_{2}^{0}

$_2^0$

Dilworth,

@Dilworth, myślę, że to dlatego, że jest zdefiniowany przy użyciu większości, a nie progu.

Kaveh

Hmm .. co dokładnie masz na myśli? Czy ma to związek z notatką Kristoffera na temat „nieograniczonych wag”?

Dilworth,

Jeśli się nie mylę, wydaje się, że udowodnienie, że hierarchia się nie zwija, jest co najmniej tak trudne, jak oddzielenie od : $\mathsf{TC^0_d}$ $\mathsf{NC^1}$ $\mathsf{TC^0}$

Oznaczmy problem Boolean Formula Evaluation przez . jest dla ramach redukcji. $BFE$ $BFE$ $\mathsf{NC^1}$ $\mathsf{AC^0}$

Autorzy: Manindra Agrawal, Eric Allender i Steven Rudich, „ Redukcje złożoności obwodu: twierdzenie o izomorfizmie i twierdzenie o luce ”, 1999, jest na pod . $BFE$ $\mathsf{NC^1}$ $\mathsf{AC^0_2}$

Załóżmy, że . Następnie dla niektórych . Dlatego . Co oznacza, że . $\mathsf{NC^1}=\mathsf{TC^0}$ $BFE \in \mathsf{TC^0_d}$ $d$ $\mathsf{NC^1} \subseteq \mathsf{TC^0_{d+2}}$ $\mathsf{TC^0} \subseteq \mathsf{TC^0_{d+2}}$

Więc dla wszystkich mamy $d$

$\mathsf{TC^0} \not\subseteq \mathsf{TC^0_d}$ implikuje i . $\mathsf{NC^1} \not\subseteq \mathsf{TC^0_{d+2}}$ $BFE \notin \mathsf{TC^0_d}$

Kaveh
źródło