Klasy złożoności, w których

21

Jedną z możliwych motywacji do badania klas złożoności obliczeniowej jest zrozumienie mocy różnych rodzajów zasobów obliczeniowych (losowość, niedeterminizm, efekty kwantowe itp.). Jeśli spojrzymy na to z tej perspektywy, wydaje się, że możemy uzyskać jeden wiarygodny aksjomat dla każdej próby scharakteryzowania, które obliczenia są wykonalne w pewnym modelu:

Każde wykonalne obliczenie może zawsze wywoływać inne wykonalne obliczenie jako podprogram. Innymi słowy, załóżmy, że programy są uważane za wykonalne do wykonania. Następnie, jeśli zbudujemy nowy program, podpinając i , tak aby wywoływał podprogramy do , wówczas ten nowy program jest również wykonalny. $P,Q$ $P$ $Q$ $P$ $Q$

Przetłumaczony na język klas złożoności ten aksjomat stanowi następujące wymaganie:

Jeśli jest klasa złożoności przeznaczony do przechwytywania, który obliczenia są możliwe w niektórych modelach, to musimy mieć . $C$ $C^C = C$

(Tutaj reprezentuje obliczeń w , które mogą powoływać wyrocznię z ,., Który jest klasą oracle złożoność) Więc nazwijmy klasa złożoność prawdopodobne , jeżeli spełnia . $C^C$ $C$ $C$ $C$ $C^C=C$

Moje pytanie: jakie znamy klasy złożoności, które są prawdopodobne (zgodnie z tą definicją wiarygodności)?

Na przykład, jest prawdopodobne, ponieważ . Czy mamy ? Co z ? Jakie są inne klasy złożoności, które spełniają to kryterium? $P$ $P^P=P$ $BPP^{BPP} = BPP$ $BQP^{BQP} = BQP$

Podejrzewam, że (a przynajmniej tak byśmy się domyślali, nawet jeśli nie możemy tego udowodnić). Czy istnieje klasa złożoności, która przechwytuje obliczenia niedeterministyczne i jest prawdopodobna, zgodnie z tą definicją? Jeśli pozwolimy oznaczać najmniejszą klasę złożoności, taką jak i , czy istnieje jakaś czysta charakterystyka tego ? $NP^{NP} \ne NP$ $C$ $NP \subseteq C$ $C^C \subseteq C$ $C$

complexity-theory oracle-machines DW
źródło

1

Zobacz to , to i to w Teoretycznej Informatyki - musisz być ostrożny.

András Salamon

OK, @ AndrásSalamon, dziękuję za ostrzeżenie i referencje! Czy możesz mi pomóc zidentyfikować sposób sformułowania mojego problemu z odpowiednią ostrożnością? Masz jakieś sugestie? Lub, jeśli odpowiedź zależy od sformułowania, czy możesz wyjaśnić, jaką odpowiedź uzyskalibyśmy przy użyciu różnych sformułowań?

DW

Stała ^ Stała = Stała.

Jozuego

13

$\mathrm{BQP}^{\mathrm{BQP}} = \mathrm{BQP}$ udowodniono w i słabych obliczeń kwantowych Bennett i in. ( arXiv ).

Zgodnie ze złożonością zoo . $\mathrm{ZBQP}^{\mathrm{ZBQP}} = \mathrm{ZBQP}$

neofita
źródło

11

Oto kilka odpowiedzi na niektóre pytania, ale na pewno nie wszystkie:

Najwyraźniej według Wikipedii mamy , , , i . Zobacz też Co to jest klasa złożoności , który zauważa, że . $P^P=P$ $BPP^{BPP}=BPP$ $PSPACE^{PSPACE}=PSPACE$ $L^L=L$ $\oplus P^{\oplus P} = \oplus P$ $\oplus P^{\oplus P}$ $\oplus P^{\oplus P} = \oplus P$

Ponadto, jeśli , to jest zamknięte pod dopełnieniem. Jest zatem mało prawdopodobne, aby : oznaczałoby to, że , co wydaje się mało prawdopodobne. Wygląda na to, że najmniejszą możliwą klasą złożoności, która zawiera jest (patrz Wikipedia ). $C^C=C$ $C$ $NP^{NP}=NP$ $NP=\textit{co-}NP$ $NP$ $PH$

Nie wiem, jaka jest sytuacja z . Nie wiem, czy istnieją inne interesujące przykłady prawdopodobnych klas złożoności. $BQP$

DW
źródło

4

Jeśli hierarchia wielomianowa zawali się na poziomie 1, tj. . Zwykle nie uważa się, że tak jest (ale jest to otwarty problem). Jeśli i , to i przez indukcję zawiera hierarchię wielomianową.

N P^{N P} = N P

$NP^{NP} = NP$

Σ_{2}^{P} = N P

$\Sigma_2^P = NP$

N P \subseteq C

$NP \subseteq C$

C^{C} \subseteq C

$C^C \subseteq C$

N P^{N P} \subseteq C

$NP^{NP} \subseteq C$

C

$C$

András Salamon

6

Klasa złożoność nazywa siebie niskim dokładnie wtedy, . Ogólnie rzecz biorąc, „lowness” był często badany w latach 80. i 90. - Google odkryje dla ciebie wiele. $C$ $C^C = C$

Ryan Williams
źródło

2

Czy możesz podać jakieś przykłady?

Ryan,

Wśród innych odpowiedzi powyżej znajdują się przykłady: P, BPP itp.

Ryan Williams

1

Zgadza się, ale czy udało Ci się znaleźć coś, o czym wcześniej nie wspomniano?

Ryan,

4

W tym komentarzu wymieniono L (logspace), NC (głębokość polilogu), P, BPP, BQP i PSPACE jako przykłady klas o niskiej złożoności.

tparker
źródło

Klasy złożoności, w których

Odpowiedzi: