¿Qué resultados de la teoría de la complejidad hacen uso esencial de la uniformidad?

Una prueba de separación de clase de complejidad utiliza la uniformidad de las clases de complejidad esencialmente si la prueba no prueba el resultado para una versión no uniforme, por ejemplo, las pruebas basadas en la diagonalización (como los teoremas de jerarquía de tiempo y espacio) hacen un uso esencial de la uniformidad, ya que necesitan simular los programas en La clase más pequeña.

¿Qué resultados en la teoría de la complejidad (aparte de las pruebas de diagonalización) utilizan esencialmente la uniformidad?

Sospechamos que Permanente requiere circuitos de tamaño superpolinomial (en cualquiera de los modelos aritméticos o booleanos). Sin embargo, si consideramos los circuitos booleanos con puertas de umbral, actualmente solo podemos probar los límites inferiores de superpolía en el caso de circuitos uniformes con restricción de profundidad . Creo que la referencia más reciente para resultados de este tipo es

"Un límite inferior superpolinomial en el tamaño de los circuitos de umbral uniforme de profundidad no constante para el permanente" por Koiran y Perifel.

(Su prueba implica la diagonalización en algún momento, por lo que esto no cumple estrictamente con su criterio, pero pensé que aún podría ser de interés).

He hecho a muchos expertos esencialmente esta pregunta, y la respuesta que siempre obtengo es: ninguna. Las pruebas de diagonalización obviamente usan la uniformidad, y estas son la base de los teoremas de la jerarquía del tiempo y el espacio, así como el tipo de límite inferior del espacio-tiempo de Fortnow-Williams. Hasta donde yo sé, todos los otros límites inferiores que conocemos, tanto para separaciones de clases de complejidad como para estructuras de datos, parecen no ser uniformes. Sería genial saber que estoy equivocado :).

Esto es solo una objeción, pero como mencionas en tu pregunta, es la simulación la que requiere uniformidad, no la diagonalización per se. Entonces, si entiendo su pregunta, eso también incluiría algo como el teorema de Savitch, que usa simulación pero no diagonalización. Por el contrario, hipotéticamente podría tener una diagonalización que no haga uso de la simulación. (No sé si eso tiene algún uso práctico, pero sé que ha habido algo de trabajo en ese sentido, incluido un artículo clásico de Kozen).

$TC^0$

$NC^1$ $TC^0$