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? $2^{O(n^\epsilon)}$ $\epsilon<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 bramek AND, OR i NOT, nieograniczony wachlarz ) (dla każdego istnieje i można uznać za ). $\mathsf{NC^1}$ $2^{O(n^\epsilon)}$ $d$ $0 <\epsilon$ $d$ $d$ $O(1/\epsilon)$

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?

cc.complexity-theory circuit-complexity bounded-depth

— Kaveh
źródło

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^{n^{o (1)}}

$2^{n^{o(1)}}$

2^{o (n)}

$2^{o(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

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

T I M E (t) \subseteq Σ_{O (d)} T I M E [n^{1 / d}]

$TIME(t) \subseteq \Sigma_{O(d)}TIME[n^{1/d}]$

E X P^{N P}

$EXP^{NP}$ mogą 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,

Cóż,

uważa się za mało prawdopodobny. Sipser (CCC '86) wykazał, że albo

albo

dla niektórych

T I M E (t) \subseteq A T I M E (t^{1 - ϵ})

$TIME(t) \subseteq ATIME(t^{1-\epsilon})$

P = R P

$P = RP$

T I M E (t) \subseteq S P A C E (t^{1 - ϵ})

$TIME(t) \subseteq SPACE(t^{1-\epsilon})$

ϵ > 0

$\epsilon > 0$ W 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 = R P

$P = RP$

— Ryan Williams

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 . $NC^1$

— 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

jeżeli odpowiedź nie jest znana bezwarunkowo.) Mamy wiesz coś takiego?

P / p o l y

$\mathsf{P/poly}$

N C

$\mathsf{NC}$

— 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