Wiemy dużo o ograniczeniach obwodów o stałej głębokości (rozmiar wielomianowy). Ponieważ formuły o stałej głębokości (rozmiar wielomianowy) są jeszcze bardziej ograniczonym modelem obliczeń, wszystkie problemy, o których wiadomo, że nie występują w AC 0, również nie są obliczalne na podstawie wzoru o stałej głębokości. Ponieważ jednak jest to łatwiejszy model, domyślam się, że w tym modelu jest więcej problemów, których nie da się obliczyć. Czy zostało to zbadane? (Zgaduję, że tak było, ale prawdopodobnie nie używam odpowiednich wyszukiwanych haseł).
Konkretnie Jestem zainteresowany następującym pytaniem: Czy jest jakaś funkcja f, które mogą być obliczane przez AC 0 obwodzie rozmiarze S, ale potrzebuje wzoru stałej głębokości rozmiarze przynajmniej Quadratic w S, lub super-wielomian w S? Jaki jest najbardziej znany wynik tego rodzaju?
W przypadku, gdy nie jest jasne, co rozumiem przez formułę o stałej głębokości, mam na myśli formułę, która jeśli wypiszesz jako drzewo (z wewnętrznymi węzłami będącymi bramkami AND / OR / NOT, a liśćmi wejściowymi), to drzewo ma stałą wysokość. Równolegle formuła o stałej głębokości jest obwodem o stałej głębokości, w którym wszystkie bramki niepochodzące mają fanout 1.