Problemy z nie są znane z ?

Jakie problemy należą do ale nie są znane z ?$\mathsf{BPP}$$\mathsf P$

Mówiąc dokładniej, interesują mnie niezależne problemy, czyli takie, których derandomizacje nie są znane jako równoważne. Na przykład wiadomo, że derandomizacja PIT i wieloczynnikowe wielomianowe rozkładanie na czynniki są równoważne i uważałbym je za jeden problem.

Motywacją mojego pytania jest to, że często mówi się, że „jest mało problemów w nie wiadomo, że w ”$\mathsf{BPP}$$\mathsf{P}$ , ale nie byłem w stanie znaleźć ich listy. W szczególności, jeśli muszę przytoczyć problemy w tej kategorii, zwykle przytaczam faktoryzację wielomianów wielowymiarowych nad polami skończonymi lub faktoryzację wielomianowych wielomianów. Przypuszczam, że istnieją przykłady, które nie są związane z rozkładem wielomianowym, na przykład w innych dziedzinach, takich jak teoria grafów lub teoria języków formalnych.

PS: Ciekawi mnie, że podobne pytanie jeszcze nie istnieje na tej stronie. Przepraszam, jeśli po prostu nie znalazłem (lub ich)!

Jeśli pytasz o niezależne problemy, możesz:

Znajdź liczbę pierwszą w przedziale , Znajdź dwie liczby pierwsze, których iloczyn znajduje się w przedziale , Znajdź trzy liczby pierwsze, których iloczyn znajduje się w przedziale , Znajdź cztery liczby pierwsze, których iloczyn znajduje się w przedziale , Znajdź pięć liczb pierwszych, których iloczyn znajduje się w przedziale , .$[N, 5N/4]$
$[N, 9N/8]$
$[N, 17N/16]$
$[N, 33N/32]$
$[N, 65N/64]$
$\ldots$

Jest niezwykle prawdopodobne, że gdybyś miał algorytm wielomianowy do rozwiązania pierwszego z nich, miałbyś algorytm wielomianowy dla wszystkich z nich. Ale nie widzę, jak formalnie zredukować którekolwiek z nich do innych. Oczywiście problem

Znajdź liczbę pierwszą w przedziale$[N, N+\log^{17} N ]$

rozwiązuje wszystkie z nich.

Istnieje szczególne zastosowanie losowości, która jest dość powszechna w sparametryzowanej złożoności, która obejmuje albo lemat izolacji , albo lemat Schwartza-Zippela . Z grubsza wymaga to zdefiniowania dużej liczby potencjalnych rozwiązań i argumentowania, że ​​wszystkie nierozwiązania „łączą się” (np. Są liczone dwukrotnie), podczas gdy pożądane rozwiązania są liczone tylko raz. Następnie albo używa się lematu izolacji, aby stworzyć sytuację z tylko jednym najmniejszym rozwiązaniem, albo definiuje duży odpowiadający wielomian formalny nad GF i używa Schwartza-Zippla, aby sprawdzić, czy istnieje niepowiązany termin. (Jestem pewien, że istnieje dobry przegląd lub ankieta, ale w tej chwili umyka mi to.)$(2^\ell)$

To powiedziawszy, mogę myśleć tylko o dwóch przypadkach, w których takie użycie doprowadziłoby do różnicy między BPP a P.

Pierwszym z nich jest najnowszy algorytm dla najkrótszych dwóch rozłącznych ścieżek ( autorski PDF ), Björklund i Husfeldt, ICALP 2014.

Drugi to problem sparametryzowany - znajdź prosty cykl przez zbiór K określonych elementów na wykresie, tj. Coś w rodzaju problemu cyklu Steiner. Gdy , problem występuje w BPP autorstwa Björklund, Husfeldt, Taslaman, SODA 2012 ( link ). (Istnieje poprzedni algorytm deterministyczny, ale jego zależność od jest wykładniczo gorsza.) Zatem można zdefiniować problem „log-Steiner Cycle” (lub jakkolwiek chcesz to nazwać), i pasowałoby do twojego pytania.$|K|=O(\log n)$$|K|$

Nie jestem ekspertem, ale być może niektóre (niezbyt naturalne?) Przykłady można bezpośrednio wyprowadzić, stosując technikę deterministycznego ograniczania problemów wyszukiwania BPP do problemów decyzyjnych BPP , przedstawionych w:

Oded Goldreich, W świecie P = BPP. Studia w zakresie złożoności i kryptografii 2011: 191–232

W szczególności patrz Twierdzenie 3.5: (redukowanie wyszukiwania do decyzji): Dla każdego problemu związanego z wyszukiwaniem BPP istnieje relacja binarna taka, że a rozwiązanie problemu wyszukiwania jest deterministycznie redukowane do pewnego problemu decyzyjnego w BPP, oznaczonego . Ponadto złożoność czasowa redukcji jest liniowa w probabilistycznej złożoności czasowej znalezienia rozwiązań dla , podczas gdy probabilistyczna złożoność czasowa$(R_{yes},R_{no})$$R$$R_{yes} \subseteq R \subseteq (\{0, 1\}^∗ \times \{0, 1\}^∗) \setminus R_{no}$$R$$\Pi$$(R_{yes},R_{no})$$\Pi$jest iloczynem kwadratowego wielomianu i gwarantowanej prawdopodobieństwa złożoności czasowej procedury decyzyjnej .$(R_{yes},R_{no})$

Twierdzenie to można rozszerzyć na ogólne problemy konstrukcyjne, na przykład (patrz wniosek 3.9 ) rozważ problem znalezienia liczby pierwszej w wystarczająco dużym przedziale czasowym:

Dla dowolnego stałego na wejściu znajdź liczbę pierwszą w przedziale$c > 7/12$$N$$[N, N + N^c]$

Randomizowany algorytm działa w oczekiwanym czasie wielomianowym; nie jest znany deterministyczny algorytm wielomianowy; ale jeśli BPP = P, taki deterministyczny algorytm wielomianowy musi istnieć (ponieważ można go zredukować do problemu decyzyjnego BPP).