Czy

21

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)2O(nϵ)ϵ<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 / ϵ )NC12O(nϵ)d0<ϵddO(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?

Kaveh
źródło
3
Jeśli przez rozmiar podwykładniczy masz na myśli (zamiast ) i przez ograniczoną głębokość rozumiesz stałą głębokość, wówczas parzystość nie ma ograniczonego rozmiaru podwykładniczego -głębokie obwody bez żadnych założeń. 2 O ( n )2no(1)2o(n)
MCH
Powinieneś opublikować swój komentarz jako odpowiedź. Otrzymasz za to kredyt i, jeśli to konieczne, można oznaczyć go jako zaakceptowaną odpowiedź. Zapobiegnie to również okresowemu automatycznemu przesłaniu pytania przez bota wspólnotowego.
Suresh Venkat
@MCH, zaktualizowałem pytanie, aby wyjaśnić, co rozumiem przez podwykładniczy rozmiar.
Kaveh
3
W jednolitym przypadku możesz coś powiedzieć ( implikuje dolne granice czasu dla SAT). Ale w przypadku niejednolitego przypadku nie znamy silnych dolnych granic dla P / poli i żadnych silnych dolnych granic dla twojej definicji obwodów o stałej głębokości wielkości sub wykładniczej. Np. Nadal jest możliwe E X P N PTIME(t)ΣO(d)TIME[n1/d]EXPNPmogą być symulowane w jednej z tych klas. Nie jestem więc pewien, co mógłbyś wyciągnąć. (Dlaczego zrobiłem z tego komentarz? Ponieważ to tak naprawdę nie jest odpowiedź ...)
Ryan Williams,
2
Cóż, uważa się za mało prawdopodobny. Sipser (CCC '86) wykazał, że albo P = R P albo T I M E ( t ) S P A C E ( t 1 - ϵ ) dla niektórych ϵ > 0TIME(t)ATIME(t1ϵ)P=RPTIME(t)SPACE(t1ϵ)ϵ>0W pewnych hipotez budowlanych ekspander, które później okazały się true Saks, Srinivasan i Zhou.This przyjęto jako dowód, że . Późniejsze prace nad twardością vs losowością sprawiły, że połączenia były bardziej precyzyjne. P=RP
Ryan Williams

Odpowiedzi:

8

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

V Vinay
źródło
Dzięki za ciekawe wskazówki. Jestem zainteresowany głównie o wysokie prawdopodobieństwo istnienia takiej symulacji (tj przypuszczenia i hipotezy, które wiązałoby się z negatywną lub pozytywną odpowiedź dla i podobnych klas, takich jak N C jeżeli odpowiedź nie jest znana bezwarunkowo.) Mamy wiesz coś takiego? P/polyNC
Kaveh
Niestety nic. Myślałem o niektórych starych gazetach Buhrmana / Homera i innych, ale nic nie pamiętam. Wrócę, jeśli coś się pojawi.
V Vinay