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 QP,QPQPQ

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 = CCCC=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 = CCCCCC CC=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 B P P B P P = B P P B Q P B Q P = B Q PPPP=PBPPBPP=BPPBQPBQP=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 ?C N P C C CC C.NPNPNPCNPCCCCC


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

Odpowiedzi:



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 .B P P B P P = B P P P S P A C E P S P A C E = P S P A C E L L = LPP=PBPPBPP=BPPPSPACEPSPACE=PSPACELL=LP PP P = PPP=PPPPP=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 N P N P = N P N P = co- N P N P P HCC=CCNPNP=NPNP=co-NPNPPH

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


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ą. Σ P 2 = N P N P C C CC N P N PC CNPNP=NPΣ2P=NPNPCCCCNPNPCC
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 = CCCC=C


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,

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.