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}$ ?

— 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