Welche Ergebnisse in der Komplexitätstheorie nutzen Uniformität wesentlich?

Ein Komplexitätsklassentrennungsbeweis verwendet die Einheitlichkeit von Komplexitätsklassen im Wesentlichen dann, wenn der Beweis das Ergebnis für eine ungleichmäßige Version nicht beweist. Beispielsweise verwenden Beweise, die auf Diagonalisierung basieren (wie Zeit- und Raumhierarchiesätze), die Einheitlichkeit wesentlich, da sie zur Simulation der Programme in erforderlich sind die kleinere Klasse.

Welche Ergebnisse in der Komplexitätstheorie (außer Diagonalisierungsnachweisen) verwenden im Wesentlichen die Einheitlichkeit?

Wir vermuten, dass Permanent Schaltungen mit Superpolynomgröße benötigt (entweder im arithmetischen oder im booleschen Modell). Wenn wir jedoch Boolesche Schaltkreise mit Schwellwertgattern betrachten, können wir derzeit Superpoly-Untergrenzen nur bei tiefenbeschränkten, einheitlichen Schaltkreisen nachweisen. Ich glaube, die jüngste Referenz für Ergebnisse dieser Art ist

"Ein Superpolynom unterer Grenzwert für die Größe gleichförmiger nichtkonstanter Grenzwertschaltungen für die bleibende Spannung" von Koiran und Perifel.

(Ihr Beweis beinhaltet irgendwann eine Diagonalisierung, so dass dies nicht genau Ihrem Kriterium entspricht, aber ich dachte, es könnte immer noch von Interesse sein.)

Ich habe im Wesentlichen vielen Experten diese Frage gestellt, und die Antwort, die ich immer bekomme, lautet: Keine. Diagonalisierungsbeweise verwenden offensichtlich Gleichförmigkeit, und diese bilden den Kern der Zeit- und Raumhierarchiesätze sowie der Fortnow-Williams-Art der Zeit-Raum-Untergrenzen. Soweit mir bekannt ist, scheinen alle anderen uns bekannten Untergrenzen, sowohl für die Trennung von Komplexitätsklassen als auch für Datenstrukturen, nicht einheitlich zu sein. Es wäre toll zu hören, dass ich mich irre :).

Dies ist nur ein Streitpunkt, aber wie Sie in Ihrer Frage anspielen, ist es die Simulation, die Gleichmäßigkeit erfordert, nicht die Diagonalisierung an sich. Wenn ich also Ihre Frage verstehe, würde das auch so etwas wie den Satz von Savitch beinhalten, der Simulation, aber keine Diagonalisierung verwendet. Umgekehrt könnten Sie hypothetisch eine Diagonale haben, die keine Simulation verwendet. (Ich weiß nicht, ob das von praktischem Nutzen ist, aber ich weiß, dass in dieser Hinsicht einige Arbeiten durchgeführt wurden, einschließlich eines klassischen Papiers von Kozen.)

$TC^0$

$NC^1$ $TC^0$