Które wyniki teorii złożoności istotnie wykorzystują jednolitość?

Dowód separacji klas złożoności używa jednorodności klas złożoności zasadniczo, jeśli dowód nie dowodzi wyniku dla wersji niejednorodnej, na przykład dowody oparte na przekątnej (takie jak twierdzenia dotyczące hierarchii czasu i przestrzeni) w istotny sposób wykorzystują jednolitość, ponieważ muszą symulować programy w mniejsza klasa.

Które wyniki teorii złożoności (inne niż dowody diagonalizacji) wykorzystują zasadniczo jednolitość?

Podejrzewamy, że Stałe wymagają obwodów wielobiegunowych (w jednym z modeli arytmetycznych lub boolowskich). Jeśli jednak weźmiemy pod uwagę obwody boolowskie z bramkami progowymi, obecnie możemy udowodnić superpolie dolne granice tylko w przypadku obwodów jednorodnych o ograniczonej głębokości . Uważam, że najnowszym odniesieniem dla wyników tego typu jest

„Superpolinomialna dolna granica wielkości jednolitych obwodów progowych o nie stałej głębokości dla stałych” autorstwa Koirana i Perifela.

(Ich dowód obejmuje w pewnym momencie przekątną, więc to nie ściśle spełnia twoje kryterium, ale pomyślałem, że może być nadal interesujące).

Zasadniczo zadałem wielu ekspertom to pytanie, a odpowiedź, na którą zawsze otrzymuję, brzmi: brak. Dowody diagonalizacji oczywiście używają jednorodności, a są one sednem twierdzeń o hierarchii czasu i przestrzeni, a także dolnych granic typu Fortnow-Williams. O ile mi wiadomo, wszystkie inne dolne granice, o których wiemy, zarówno w przypadku separacji klas złożoności, jak i struktur danych, wydają się niejednolite. Byłoby wspaniale usłyszeć, że się mylę :).

To tylko spór, ale jak wspominasz w swoim pytaniu, to symulacja wymaga jednolitości, a nie diagonalizacji per se. Jeśli więc rozumiem twoje pytanie, obejmuje to również twierdzenie Savitcha, które wykorzystuje symulację, ale nie diagonalizację. I odwrotnie, możesz mieć hipotetyczną diagonalizację, która nie korzysta z symulacji. (Nie wiem, czy ma to jakieś praktyczne zastosowanie, ale wiem, że było trochę pracy w tym stylu, w tym klasyczny artykuł Kozen).

$TC^0$

$NC^1$ $TC^0$