¿Cuáles son ejemplos de cómo la no uniformidad puede ser útil?

Tengo curiosidad acerca de las formas en que ha visto que la falta de uniformidad es útil en el cálculo. Una forma es la aleatoriedad, como en , y otra son las tablas de búsqueda que se utilizan para mostrar que todos los idiomas tienen circuitos no uniformes.$BPP \subseteq P/poly$

En particular, estoy interesado en las formas en que los objetos que se sabe que existen a través del método probabilístico y otros métodos de prueba no constructivos (o no lo suficientemente constructivos) se pueden aprovechar utilizando la no uniformidad. Prefiero que los ejemplos sean naturales, no artificiales. Para ser claros, un circuito para un problema artificial podría ser algo así como: dado un lenguaje , creo un circuito de tamaño polinómico calculando una función realmente difícil usando mi consejo y preguntando si$L \in P$f ( | x | ) n / | f ( | x | ) | ⊕ x ∈ $f(|x|)$$f(|x|)^{n/|f(|x|)|} \oplus x \in L$ .

Un ejemplo que me gusta es el argumento de que contando cadenas en el idioma (véase, por ejemplo, https://blog.computationalcomplexity.org/2004/01/little-theorem.html ) .$\mathrm{NE\subseteq coNE}/(n+1)$

Un ejemplo es . Este teorema fue probado por Reinhardt y Allender en su artículo "Making Unondeterminism Unmbiguous" . Sin entrar en detalles, el consejo en su algoritmo consiste en una secuencia de asignaciones de peso de borde de modo que para cualquier dígrafo G codificado por una cadena de n bits, alguna asignación en la secuencia hace que G sea "único-mínimo". Se puede demostrar que dicha secuencia existe por el método probabilístico. La contribución principal de Reinhardt y Allender fue proporcionar algoritmos inequívocos de espacio logarítmico para determinar qué asignación en la secuencia funciona para un determinado dígrafo $\mathbf{NL} \subseteq \mathbf{UL}/\text{poly}$$G$$n$$G$$G$y para decidir conectividad s - t en un dígrafo minimo.$s$$t$

Al igual que con , se conjetura que la falta de uniformidad en realidad no es necesario aquí, es decir, se conjetura que N L = U L .$\mathbf{BPP} \subseteq \mathbf{P}/\text{poly}$$\mathbf{NL} = \mathbf{UL}$

No estoy seguro de si se ajusta a lo que está buscando, pero hay algunos resultados que demuestran los teoremas de jerarquía para las clases de complejidad semántica con un poco de consejo, donde no se conoce ningún teorema de jerarquía sin consejo. El ejemplo más conocido es BPP, para el cual no conocemos un teorema de jerarquía, pero Fortnow y Santhanam mostraron que existe con un poco de consejo (basándose en un resultado de Barak que utilizó más consejos). Este artículo de Melkebeek y Pervyshev da referencias y la historia, y un teorema que parece subsumir a los anteriores.