Jakie są przykłady tego, jak niejednolita może być przydatna?

Ciekawi mnie, w jaki sposób niejednorodność okazała się przydatna w obliczeniach. Jednym ze sposobów jest losowość, jak w$BPP \subseteq P/poly$, a kolejnym są tabele przeglądowe, które służą do pokazania, że ​​wszystkie języki mają niejednolite obwody.

W szczególności interesują mnie sposoby, w jakie obiekty, o których wiadomo, że istnieją za pomocą metody probabilistycznej i innych niekonstruktywnych (lub niewystarczająco konstruktywnych) metod dowodowych, można wykorzystać przy użyciu niejednorodności. Wolałbym, żeby przykłady były naturalne, a nie wymyślone. Mówiąc wprost, obwód dla wymyślonego problemu może być czymś w rodzaju: biorąc pod uwagę jakiś język$L \in P$, Tworzę obwód wielkości wielomianowej, obliczając naprawdę trudną funkcję $f(|x|)$ korzystając z moich rad i pytając, czy $f(|x|)^{n/|f(|x|)|} \oplus x \in L$.

Przykładem, który podoba mi się, jest argument, że $\mathrm{NE\subseteq coNE}/(n+1)$zliczając ciągi w języku (patrz np. https://blog.computationalcomplexity.org/2004/01/little-theorem.html ).

Jednym z przykładów jest $\mathbf{NL} \subseteq \mathbf{UL}/\text{poly}$. Twierdzenie to zostało udowodnione przez Reinhardta i Allendera w ich pracy „Czynienie niedeterminizmu jednoznacznym” . Bez wchodzenia w szczegóły rada w ich algorytmie składa się z sekwencji przypisań wagi krawędzi, tak że dla każdego wykresu$G$ kodowane przez $n$-bit string, pewne przypisanie w sekwencji sprawia $G$„min-niepowtarzalny”. Taką sekwencję można wykazać za pomocą metody probabilistycznej. Głównym wkładem Reinhardta i Allendera było podanie jednoznacznych algorytmów przestrzeni logów w celu ustalenia, które przypisanie w sekwencji działa dla danego danego wykreślnika$G$ i do decydowania $s$-$t$ łączność na minimografie digraph.

Jak z $\mathbf{BPP} \subseteq \mathbf{P}/\text{poly}$, przypuszcza się, że niejednorodność nie jest tutaj faktycznie potrzebna, tzn. zakłada się, że $\mathbf{NL} = \mathbf{UL}$.

Nie jestem pewien, czy pasuje do tego, czego szukasz, ale istnieje kilka wyników potwierdzających twierdzenia o hierarchii dla klas złożoności semantycznej z jedną radą, w przypadku których żadne twierdzenie o hierarchii nie jest znane bez porady. Najbardziej znanym przykładem jest BPP, dla którego nie znamy twierdzenia o hierarchii, ale Fortnow i Santhanam pokazali, że istnieje z jedną radą (bazując na wyniku Baraka, który wykorzystał więcej rad). W tym artykule Melkebeek i Pervyshev podaje odniesienia i historię oraz twierdzenie, które wydaje się obejmować poprzednie.