1
Czy
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)2)O ( nϵ)2O(nϵ)2^{O(n^\epsilon)}ϵ < 1ϵ<1\epsilon<1re= O ( 1 )d=O(1)d = O(1) Wiemy, że każdą funkcję obliczalną przez obwód można obliczyć na podstawie obwodu głębokości (używając …