Czy przypadkowość kupuje nam coś w środku P?

Niech będzie klasą problemów decyzyjnych mających ograniczony algorytm losowego błędu dwustronnego działający w czasie . $\mathsf{BPTIME}(f(n))$ $O(f(n))$

Czy znamy żadnego problemu takie, że , ale ? Czy udowodniono jego nieistnienie? $Q \in \mathsf{P}$ $Q \in \mathsf{BPTIME}(n^k)$ $Q \not \in \mathsf{DTIME}(n^k)$

To pytanie zostało zadane tutaj na cs.SE , ale nie uzyskało zadowalającej odpowiedzi.

— aelguindy
źródło

(1) BPP (f (n)) jest zwykle oznaczane jako BPTIME (f (n)). (2) W kontekście złożoności obliczeniowej uważam, że jest to otwarte. (Znanych jest wiele przykładów w złożoności zapytania i ustawieniach złożoności komunikacji.) (3) Gdyby jego nieistnienie zostało już udowodnione, to już byśmy wiedzieli, że P = BPP.

— Tsuyoshi Ito,

Nawiasem mówiąc, w pytaniu na cs.stackexchange.com masz pewne nieporozumienie na temat relacji między BPTIME i ZPTIME, i może to być część powodu, dla którego nie otrzymałeś zadowalającej odpowiedzi.

— Tsuyoshi Ito,

@TsuyoshiIto Dzięki, nie zgadzam się, że jeśli mamy udowodnić nieistnienia wtedy wiemy,

, jestem ograniczając ustawienie na problemy w

. Może

, podczas gdy

P = B P P

$P=BPP$

P

$P$

B P T I M E (n^{k}) \cap P = D T I M E (n^{k})

$BPTIME(n^k) \cap P = DTIME(n^k)$

ogólnie, czy coś mi brakuje? Można też proszę zwrócić uwagę na mojego nieporozumień

, może brakowało mi satysfakcjonującej odpowiedzi wręcz ..

B P T I M E (n^{k}) \neq D T I M E (n^{k})

$BPTIME(n^k) \neq DTIME(n^k)$

B P T I M E

$BPTIME$

Z P T I M E

$ZPTIME$

— aelguindy

Twoje pytanie nie mówi, że ograniczasz problem Q do bycia w P. Jeśli taka jest Twoja intencja, edytuj pytanie.

— Tsuyoshi Ito

W celu przybliżenia 1-mediany skończonej przestrzeni metrycznej z kilkoma zapytaniami do funkcji odległości, losowy punkt daje przybliżone oczekiwanie 2 i przybliżenie (2 + eps) z dużym prawdopodobieństwem. Ale żaden algorytm deterministyczny, który pytałby

funkcję odległości

razy, nie byłby lepszy niż przybliżenie 4-krotne. [ Chang 2013 ]

o (n^{2})

$o(n^2)$

— Neal Young,

Odpowiedzi:

Innym przykładem jest oszacowanie objętości wielościanu w wysokich wymiarach. Istnieje bezwarunkowa dolna granica strategii deterministycznych mających na celu przybliżenie objętości nawet do współczynnika wykładniczego, ale istnieje problem FPRAS.

Aktualizacja: odpowiedni artykuł to (link do pliku PDF ):

I. Barany i Z. Furedi. Obliczanie objętości jest trudne, Discrete and Computational Geometry 2 (1987), 319-326.

— Suresh Venkat
źródło

Czy możesz podać odniesienie do bezwarunkowej dolnej granicy?

— T ....

dodane odniesienie.

— Suresh Venkat

Problem : Tablica składa się z 1s i 0s. Znajdź takie, że wynosi 1. $A[1..2n]$ $n$ $n$ $i$ $A[i]$

Możesz zapytać „Który numer jest obecny w ”? Każde zapytanie zajmuje stały czas. $A[i]$

Rozwiązanie : algorytm losowy: wybierz losowy indeks i sprawdź, czy $i$ $A[i]$ wynosi 1. Oczekiwana liczba zapytań wynosi 2, ale dowolny algorytm deterministyczny musi wykonać co najmniej zapytań. Dlatego zrandomizowana górna granica jest ściśle lepsza niż deterministyczna dolna granica w tym modelu. $n$

Jest to przykład złożoności zapytania, do którego Tsuyoshi odwoływał się w komentarzu.

— Jagadish
źródło

W najgorszym przypadku dowolny algorytm deterministyczny musi wykonać co najmniej

zapytań .

n

$n$

— argentpepper

Co rozumiesz przez „obecnie nie znamy żadnego nietrywialnego dowodu na dolną granicę dla jakiegokolwiek problemu w NP (nie mówiąc już o P)”?

— Kristoffer Arnsfelt Hansen

Być może niechlujnie użyłem słowa „nietrywialne”. Miałem na myśli „Obecnie nie możemy udowodnić bezwarunkowej dolnej granicy

dla

dla SAT ani żadnego problemu w NP”. Czy to jest poprawne?

Ω (n^{k})

$\Omega(n^k)$

k > 0

$k>0$

— Jagadish,

Cóż, może nie dla „ładnych” problemów, takich jak SAT; ale pamiętajmy, że mamy takie dolne granice dla innych problemów z twierdzeń o hierarchii czasu. Pytanie nie dotyczy „ładnych” problemów, ale klas złożoności.

— Kristoffer Arnsfelt Hansen

Ah, tak. Zakładałem, że OP był zainteresowany problemami naturalnymi. Zredagowałem swoją odpowiedź.

— Jagadish

Biorąc pod uwagę macierz wypłat dla macierzy sumy zerowej z wypłatami w [0,1], oszacuj wartość gry w dodatku . $n\times n$ $\epsilon$

Ten problem ma algorytm losowy, który działa w czasie , który (co jest możliwe) żaden algorytm deterministyczny nie może dopasować [ GK95 ]. $O(n\log^2(n)/\epsilon^2)$

Zobacz także Wydajne i proste algorytmy randomizowane, w których determinizm jest trudny .

— Neal Young
źródło