Quels résultats de la théorie de la complexité font un usage essentiel de l'uniformité?

Une preuve de séparation de classes de complexité utilise l'uniformité des classes de complexité essentiellement si la preuve ne prouve pas le résultat pour une version non uniforme, par exemple les preuves basées sur la diagonalisation (comme les théorèmes de hiérarchie temporelle et spatiale) font un usage essentiel de l'uniformité car elles doivent simuler les programmes dans la petite classe.

Quels résultats de la théorie de la complexité (autres que les preuves de diagonalisation) utilisent essentiellement l'uniformité?

Nous pensons que Permanent nécessite des circuits de taille superpolynomiale (dans les modèles arithmétiques ou booléens). Cependant, si nous considérons les circuits booléens avec des portes de seuil, nous ne pouvons actuellement prouver des limites inférieures superpolaires que dans le cas de circuits uniformes à profondeur limitée . Je pense que la référence la plus récente pour les résultats de ce type est

"Une limite inférieure superpolynomiale sur la taille des circuits de seuil uniformes à profondeur non constante pour le permanent" par Koiran et Perifel.

(Leur preuve implique la diagonalisation à un moment donné, donc cela ne répond pas à proprement parler à votre critère, mais j'ai pensé que cela pourrait toujours être intéressant.)

J'ai essentiellement posé cette question à de nombreux experts, et la réponse que j'obtiens toujours est: aucune. Les preuves de diagonalisation utilisent évidemment l'uniformité, et elles sont au cœur des théorèmes de la hiérarchie du temps et de l'espace, ainsi que des bornes inférieures de l'espace-temps de type Fortnow-Williams. Pour autant que je sache, toutes les autres limites inférieures que nous connaissons, à la fois pour les séparations de classes de complexité et pour les structures de données, semblent être non uniformes. Ce serait bien d'entendre que je me trompe cependant :).

Ce n'est qu'un petit problème, mais comme vous y faites allusion dans votre question, c'est la simulation qui nécessite l'uniformité, pas la diagonalisation en soi. Donc, si je comprends votre question, cela inclurait également quelque chose comme le théorème de Savitch, qui utilise la simulation mais pas la diagonalisation. Inversement, vous pourriez hypothétiquement avoir une diagonalisation qui ne fait pas appel à la simulation. (Je ne sais pas si cela est d'une utilité pratique, mais je sais qu'il y a eu un certain travail dans ce sens, y compris un papier classique de Kozen.)

$TC^0$ fait un usage essentiel de l'uniformité. Voir " Le permanent nécessite de grands circuits de seuil uniformes ".

$NC^1$ $TC^0$