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.

cc.complexity-theory ds.algorithms randomized-algorithms derandomization 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