Quais são os exemplos de como a não uniformidade pode ser útil?

Estou curioso sobre as maneiras pelas quais você viu a não uniformidade ser útil na computação. Uma maneira é a aleatoriedade, como em , e outra são as tabelas de consulta que são usadas para mostrar que todos os idiomas têm circuitos não uniformes.$BPP \subseteq P/poly$

Em particular, estou interessado em maneiras pelas quais objetos que existem por meio do método probabilístico e outros métodos de prova não construtivos (ou não construtivos o suficiente) podem ser aproveitados usando a não uniformidade. Eu preferiria que os exemplos fossem naturais, não artificial. Para ser claro, um circuito para um problema artificial pode ser algo como: dada a linguagem , eu crio um circuito de tamanho polinomial calculando uma função realmente difícil usando meu conselho e perguntando se f (| x |) ^ {n / | f (| x |) |} \ oplus x \ in L .f ( | x |$L \in P$$f(|x|)$$f(|x|)^{n/|f(|x|)|} \oplus x \in L$

Um exemplo que eu gosto é o argumento que contando seqüências de caracteres no idioma (consulte, por exemplo, https://blog.computationalcomplexity.org/2004/01/little-theorem.html )$\mathrm{NE\subseteq coNE}/(n+1)$

Um exemplo é . Esse teorema foi comprovado por Reinhardt e Allender em seu artigo "Tornando o não-determinismo inequívoco" . Sem entrar em detalhes, o conselho em seu algoritmo consiste em uma sequência de atribuições de peso de borda, de modo que, para qualquer dígrafo codificado por uma seqüência de bits, alguma atribuição na sequência torne "min-único". Pode-se demonstrar que essa sequência existe pelo método probabilístico. A principal contribuição de Reinhardt e Allender foi fornecer algoritmos inequívocos de espaço de log para descobrir qual atribuição na sequência funciona para um determinado dígrafo e para decidirG n G G s $\mathbf{NL} \subseteq \mathbf{UL}/\text{poly}$$G$$n$$G$$G$$s$- conectividade em um dígrafo min-exclusivo.$t$

Assim como no , é conjecturado que a não uniformidade não é realmente necessária aqui, ou seja, é conjecturado que .N L = U $\mathbf{BPP} \subseteq \mathbf{P}/\text{poly}$$\mathbf{NL} = \mathbf{UL}$

Não tenho certeza se ele se encaixa no que você está procurando, mas existem alguns resultados que provam teoremas de hierarquia para classes de complexidade semântica com um pequeno conselho, em que nenhum teorema de hierarquia é conhecido sem aconselhamento. O exemplo mais conhecido é o BPP, para o qual não conhecemos um teorema da hierarquia, mas Fortnow e Santhanam mostraram que existe um com um pouco de conselho (baseado no resultado de Barak que usou mais conselho). Este artigo de Melkebeek e Pervyshev fornece referências e a história, e um teorema que parece subsumir os anteriores.