Czy można zastosować ograniczenia losowe, aby uzyskać dolną granicę dla

Istnieje wiele dobrze znanych wielkości obwód dolny związanego wyniki w oparciu o losowe ograniczeń i przełączania lematu . $\mathsf{AC^0}$

Czy możemy opracować wynik zamiany lematu, aby udowodnić niższą wielkość dla obwodów $\mathsf{TC^0}$ (podobnie do dolnej granicy dla $\mathsf{AC^0}$ )?

Czy jest jakaś nieodłączna przeszkoda w stosowaniu tego podejścia do udowodnienia dolnych granic $\mathsf{TC^0}$ ?

Czy wyniki barier, takie jak naturalne dowody, mówią coś o stosowaniu technik podobnych do lematu do udowodnienia dolnej granicy $\mathsf{TC^0}$ ?

cc.complexity-theory circuit-complexity lower-bounds boolean-functions Jeigh
źródło

Czy znasz dowód przełączenia lematu na

A C^{0}

$\mathsf{AC^0}$ ?

Kaveh

Przeczytałem niższy rozdział obwodu podręcznika Arory. Po pierwsze, przekształć dowolny obwód o stałej głębokości w obwód bez bramek NIE z przeplatającymi się warstwami AND-OR, a po drugie za pomocą przełącznika Switching Lemma tę dwie warstwy, w końcu otrzymujemy szczyt obwodu, a drugi poziom to te same bramki AND (lub OR) w ten sposób możemy pozbawić obwód jednej warstwy, zmniejszając głębokość obwodu.

Jeigh,

Jednak obserwowanie wyjścia bramki nie jest prostsze niż przypadek logiczny, gdy naprawiamy kilka wartości danych wejściowych (w przypadku logicznym naprawiamy dane dotyczące pierwiastka kwadratowego n). Bramka AND i OR to ekstremalna wersja bram progowych i znacznie łatwiejsza do zaobserwowania wpływ ograniczeń.

Jeigh

A C^{0}

$\mathsf{AC^0}$

\land

$\land$

\lor

$\lor$

\mod p

$\mod p$

\mod p

$\mod p$

Zauważ też, że losowe ograniczenia i Przełączająca lemat są jednym z głównych przykładów dowodów naturalnych. W każdym razie, mam nadzieję, że ekspert od złożoności obwodu opublikuje bardziej kompleksową odpowiedź. ps: Pozwoliłem sobie na przepisanie pytania, możesz cofnąć, jeśli nie podoba ci się moja edycja.

Kaveh

Odpowiedzi:

Możliwe jest wykorzystanie losowych ograniczeń w celu udowodnienia niższych granic obwodów progowych.

W szczególności w artykule Kompromisy między głębokością a wielkością dla obwodów progowych , Impagliazzo, Paturi i Saks stosują losowe ograniczenia, aby udowodnić dolną granicę superlinii (liczbę drutów) dla obwodów progowych o stałej głębokości obliczających funkcję parzystości.

Jeśli chodzi o udowodnienie superminomialnych dolnych granic dla obwodów to tak, istotna jest koncepcja naturalnego dowodu, ponieważ istnieją konstrukcje generatorów funkcji pseudolosowych w . $\mathsf{TC}^0$ $\mathsf{TC}^0$

Kristoffer Arnsfelt Hansen
źródło

Zobacz także najnowszy artykuł Daniela Kane'a i Ryana Williamsa, Brama Superliniowa i Dolne granice drutu supertwadratowego dla obwodów progowych głębokości 2 i 3 (STOC 2016).

Ryan opisuje artykuł w następujący sposób (poniższy opis pochodzi z jego strony głównej):

Dajemy wyraźną funkcję w dla której każda większość liniowych obwodów progowych o głębokości dwóch (z nieograniczonymi ciężarami) potrzebuje około bramek i przewodów jednocześnie. Pokazujemy również, że funkcja Andreeva (obliczalna na podstawie obwodu większości o głębokości trzech głębokości o rozmiarze ) wymaga, aby ta sama bramka i dolna granica drutu były obliczane z liniowymi obwodami progowymi o głębokości 2. Kluczowym narzędziem jest Littlema-Offord Lemma, której używamy do analizy wpływu losowych ograniczeń na wejścia obwodów progowych o małej głębokości. $\mathsf{PP}$ $n^{1.5}$ $n^{2.5}$ $O(n)$

Yuval Filmus
źródło