Pytania otagowane jako complexity-classes

Klasy złożoności obliczeniowej i ich relacje

1
Utrzymanie porządku na liście w w Czas
Problem z utrzymaniem porządku (lub „utrzymaniem porządku na liście”) polega na obsłudze operacji: singleton: tworzy listę z jednym elementem, zwraca do niej wskaźnik insertAfter: dany wskaźnik do elementu wstawia nowy element po nim, zwracając wskaźnik do nowego elementu delete: dany wskaźnik do elementu usuwa go z listy minPointer: biorąc pod …
3
Teorie charakteryzujące klasy złożoności obliczeniowej
Czytając artykuł „ Teoria aplikacyjna dla FPH ”, można natknąć się na następujący fragment: Biorąc pod uwagę teorie charakteryzujące klasy złożoności obliczeniowej, istnieją trzy różne podejścia: w jednym funkcje, które można zdefiniować w teorii, są „automatycznie” w ramach pewnej klasy złożoności. Na takim koncie należy ograniczyć składnię, aby zagwarantować, że …
2
Czy APX jest zawarty w NP?
Mówi się, że problem P występuje w APX, jeśli istnieje pewna stała c> 0, tak że istnieje algorytm aproksymacji czasu wielomianowego dla P ze współczynnikiem aproksymacji 1 + c. APX zawiera PTAS (widoczne po prostu przez wybranie dowolnej stałej c> 0) i P. Czy APX jest w NP? W szczególności, …
1
vs
W naszej ostatniej pracy rozwiązujemy problem obliczeniowy, który powstał w kontekście kombinatorycznym, przy założeniu, że , gdzie to -wersja . Jedyny artykuł na temat , który znaleźliśmy, to artykuł Beigel-Buhrman-Fortnow 1998 , cytowany w Zoo Complexity . Rozumiemy, że możemy wziąć wersje parzystości problemy (zobacz to pytanie ), ale być …
5
Jaka jest klasa złożoności podprogramów kwantowych przyjmujących dowolne stany kwantowe jako dane wejściowe?
Klasa złożoności BQP odpowiada podprogramom kwantowym w czasie wielomianowym, przyjmującym klasyczne dane wejściowe i wyrzucającym probabilistyczny sygnał klasyczny. Porada kwantowa modyfikuje to, aby uwzględnić kopie niektórych z góry określonych stanów porady kwantowej, ale jak zwykle z klasycznymi danymi wejściowymi. Jaka jest klasa złożoności podprogramów kwantowych czasu wielomianowego przyjmujących dowolne stany …
2
Analogi kwantowe klas złożoności SPACE
Często rozważamy klasy złożoności, w których jesteśmy ograniczeni ilością miejsca, które może wykorzystać nasza maszyna Turinga, na przykład: DSPACE(f(n))DSPACE(f(n))\textbf{DSPACE}(f(n)) lub NSPACE(f(n))NSPACE(f(n))\textbf{NSPACE}(f(n)) . Wydaje się, że we wczesnej teorii złożoności odniesiono duży sukces z tymi klasami, takimi jak twierdzenie o hierarchii przestrzeni i tworzenie ważnych klas, takich jak LL\textbf{L} i PSPACEPSPACE\textbf{PSPACE} …
1
Problemy w NC nie są znane z NC2
Czy istnieją interesujące problemy, które występują w ale nie są znane w N C 2 ? W artykule „taksonomii problemów z szybkim Równoległe algorytmy” Kucharz wspomina, że MIS był znany tylko w N C 5 , ale od tego czasu została sprowadzona do N C 2 . Zastanawiam się, czy …
1
Beigel-Tarui transformacja układów ACC
Czytam dodatek na temat dolnych granic ACC dla NEXP w książce Arora i Barak's Computational Complexity . http://www.cs.princeton.edu/theory/uploads/Compbook/accupt.pdf Jednym z kluczowych lematów jest transformacja z obwodów w wielomianowe wielomianowe nad liczbami całkowitymi o stopniu polilogarytmicznym i quasipolynomialnym współczynnikami lub równoważnie , klasa obwodów S Y M + , która jest …
2
Czy Parity-P jest zawarty w PP?
To pytanie zadał Jan Pax na liście mailingowej Podstawy matematyki . Z pewnością ale z odpowiedzi na to pytanie podejrzewam , że nie wiadomo, czy ⊕ P ⊆ P P (inaczej P P byłaby jedną z możliwych odpowiedzi na to pytanie). Jeśli nie wiadomo, czy istnieje separacja wyroczni?P⊕P⊆P#P=PPPP⊕P⊆P#P=PPPP^{\oplus P} \subseteq …
1
Jak problem może występować w NP, być trudnym NP, a nie kompletnym NP?
Najdłużej myślałem, że problem był NP-zupełny, jeśli jest zarówno (1) NP-trudny, jak i (2) jest w NP. Jednak w słynnym artykule „Metoda elipsoidy i jej konsekwencje w optymalizacji kombinatorycznej” autorzy twierdzą, że problem ułamkowej liczby chromatycznej należy do NP i jest trudny do NP, ale nie jest znany jako NP-zupełny. …
1
kontra
Wiem, że PNP[logn]PNP[log⁡n]\mathsf{P}^{\mathsf{NP}[\log n]} (logarytmicznie wiele wywołań do NP oracle) jest równoważne PNP||PNP||\mathsf{P}^{\mathsf{NP}||}(wielomianowa liczba równoległych zapytań do NP oracle). Zastanawiałem się, czy wersja „funkcyjna” tych klas również jest równoważna, to znaczy czy Jeśli wiadomo, że to prawda, wskaźnik byłby naprawdę pomocny.FPNP[logn]=FPNP||FPNP[log⁡n]=FPNP|| \mathsf{FP}^{\mathsf{NP}[\log n]} = \mathsf{FP}^{\mathsf{NP}||}
3
Złożoność sprawdzania, czy dwa CNF mają taką samą liczbę rozwiązań
Biorąc pod uwagę dwa CNF, jeśli mają taką samą liczbę zadań, aby były prawdziwe, odpowiedz „Tak”, w przeciwnym razie odpowiedz „Nie”. Łatwo zauważyć, że jest to w , ponieważ jeśli znamy dokładną liczbę rozwiązań dla tych dwóch CNF, po prostu je kampanujemy i odpowiadamy „Tak” lub „Nie”.P#PP#PP^{\#P} Jaka jest złożoność …
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.