Czy istnieje jakakolwiek prawdopodobna hipoteza złożoności / kryptografii, która wyklucza możliwość, że obwody wielomianowe mają rozmiar podwykładniczy (tj. z ) ograniczoną głębokością ( ) obwody? ϵ<1d=O(1)
Wiemy, że każdą funkcję obliczalną przez obwód można obliczyć na podstawie obwodu głębokości (używając bramek AND, OR i NOT, nieograniczony wachlarz ) (dla każdego istnieje i można uznać za ). 2 O ( n ϵ ) d 0 < ϵ d d O ( 1 / ϵ )
Pytanie brzmi:
czy istnieje powód, który spowodowałby, że istnienie takich obwodów dla ogólnych obwodów wielomianowych jest mało prawdopodobne?
Odpowiedzi:
To, o co prosisz, powinno mieć złe konsekwencje, ale nie mogę o tym myśleć natychmiast. Mam więc tylko kilka wskazówek do tego, co wiemy.
Sprawdź Violę na temat mocy obliczeń na małej głębokości . Najbardziej znaną konstrukcją Valiant dla obwodów boolowskich jest: obwody o wielkości logarytmicznej o głębokości do 3 obwodów podwyrazowych. (Wiemy lepiej o obwodach arytmetycznych .) Istnieją również niektóre wyniki Beigel / Tarui na ACC, zawarte w obwodach o ograniczonej głębokości o wielkości superpolii. Nie przypominam sobie jednak, by obejmowało to cały .NC1
źródło