Pytania otagowane jako complexity-classes

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

1
Jakie mamy dowody na ?
Zgodnie z sugestią Josha Grochowa przekształcam swój komentarz z poprzedniego pytania w nowe pytanie. Jakie mamy dowody na ?UP≠NPUP≠NP\mathsf{UP} \neq \mathsf{NP} Tutaj to klasa języków rozpoznawalnych przez niedeterministyczne maszyny Turinga o wielomianowym czasie, które mają unikalną ścieżkę akceptacji w instancjach „tak” i brak ścieżki akceptacji w instancjach „nie”.UPUP\mathsf{UP} Oczywiście , …
3
W jakiej klasie są algorytmy losowe, które mają błąd z dokładnie 25% szansą?
Załóżmy, że rozważam następujący wariant BPP, który pozwala nam nazywać się E (xact) BPP: Język jest w EBPP, jeśli istnieje wielomianowy losowy czas TG, który akceptuje każde słowo z prawdopodobieństwem dokładnie 3/4 i każde słowo nie w język z prawdopodobieństwem dokładnie 1/4. Oczywiście EBPP jest zawarty w BPP, ale czy …
1
Jaka jest złożoność tego problemu kolorowania krawędzi?
Ostatnio spotkałem następujący wariant kolorowania krawędzi. Biorąc pod uwagę połączony niekierowany wykres, znajdź kolorystykę krawędzi, która wykorzystuje maksymalną liczbę kolorów, jednocześnie spełniając ograniczenie, że dla każdego wierzchołka krawędzie padające na v używają co najwyżej dwóch kolorów.vvvvvv Po pierwsze sądzę, że problem jest trudny do rozwiązania. Klasyczne twarde proofy NP na …
2
Czy
W „ostatnim akapicie” „pierwszej strony” następującego artykułu: Vikraman Arvind , Johannes Köbler , Uwe Schöning , Rainer Schuler , „Jeśli NP ma obwody wielomianowe, wówczas MA = AM”, Theoretical Computer Science, 1995. Napotkałem nieco sprzeczne z intuicją twierdzenie: (ΣP2∩ΠP2)NP=ΣP3∩ΠP3(Σ2P∩Π2P)NP=Σ3P∩Π3P(\Sigma^P_2 \cap \Pi^P_2)^{NP} = \Sigma^P_3 \cap \Pi^P_3 Myślę, że powyższa tożsamość została …
1
Klasy złożoności dla dowodów wiedzy
Pytanie zadane mi przez Grega Kuperberga. Zastanawiam się, czy są jakieś prace, które definiują i badają złożoność klas języków dopuszczających różnego rodzaju dowody wiedzy . Klasy takie jak SZK i NISZK są niezwykle naturalne z punktu widzenia złożoności, nawet jeśli całkowicie zapomnieliśmy o zerowej wiedzy i po prostu zdefiniowaliśmy je …
3
Przykłady
Potrzebuję listę pełnych językach. Istnieją dwa takie problemy wymienione w zoo złożoności , a mianowicie:Σp2Σ2p\Sigma_2^p Minimalny równoważny DNF. Biorąc pod uwagę formułę DNF F i liczbę całkowitą k, czy istnieje formuła DNF równoważna F z k lub mniejszą liczbą literałów? Najkrótszy implant. Biorąc pod uwagę wzór F i liczbę całkowitą …
1
Czy ciągła dwuznaczność może zmniejszyć złożoność stanu zwykłych języków?
Mówimy, że NFA jest stale niejednoznaczny, jeśli istnieje tak że każde słowo jest akceptowane przez lub (dokładnie) ścieżek.MMMk∈Nk∈Nk\in \mathbb{N}w∈Σ∗w∈Σ∗w\in \Sigma^*000kkk Jeśli automat jest stale niejednoznaczny dla , wówczas nazywa się Jednoznacznym FA (UFA).MMMk=1k=1k=1MMM Niech będzie zwykłym językiem.LLL Czy jakiś stale dwuznaczny automat dla być mniejszy niż najmniejszy UFA, który akceptuje …
2
Dobra referencja dla operatorów klasy złożoności?
Interesuje mnie, czy istnieją jakieś dobre artykuły ekspozycyjne lub ankiety, do których mogę się odnieść, pisząc o operatorach klas złożoności : operatorach, które przekształcają klasy złożoności, np. Dodając do nich kwantyfikatory. Przykłady operatorów Poniższe można interpretować jako absolutną minimalną listę operatorów, którą odpowiedź powinna umieć opisać. Tutaj jest dowolnym zestawem …
3
Separacje klas złożoności bez twierdzeń hierarchicznych
Twierdzenia o hierarchii są podstawowymi narzędziami. Wiele z nich zebrano we wcześniejszym pytaniu (patrz Jakie hierarchie i / lub twierdzenia dotyczące hierarchii znasz? ). Niektóre separacje klas złożoności wynikają bezpośrednio z twierdzeń hierarchicznych. Przykłady takich dobrze znanych separacji: L ≠ PS.P.A C.miL≠PSPACEL\neq PSPACE , , , .N P ≠ N …
2
Charakterystyka problemów, dla których istnieją algorytmy czasu podliniowego
Zastanawiałem się, czy problemy, dla których istnieją algorytmy czasu podliniowego (w wielkości wejściowej), można scharakteryzować jako posiadające określone właściwości. Obejmuje to czas podliniowy (np. Testowanie właściwości, alternatywne pojęcie przybliżenia problemów decyzyjnych), przestrzeń podliniowa (np. Algorytmy szkicowania / przesyłania strumieniowego, w których maszyna Turinga ma taśmę tylko do odczytu, podliniową przestrzeń …
1
Problemy z logDCFL-complete
LogCFL to zestaw wszystkich języków, które można sprowadzać do przestrzeni logicznej do języka bezkontekstowego. Podobnie LogDCFL jest zbiorem wszystkich języków, które są przestrzenią logiczną redukowalną do deterministycznego języka bezkontekstowego. Zobacz ten artykuł na Wikipedii, aby zapoznać się z niektórymi naturalnymi problemami związanymi z logCFL. Istnieje kilka innych interesujących problemów z …
1
Gładka złożoność nieujemnego stałego
Od dwóch dekad trwają fantastyczne prace nad Permanentnym. Przez pewien czas zastanawiałem się nad możliwością zastosowania algorytmu Smooth P dla Permanent of Nonnegative Matrices. Istnieje oczywiście słynny algorytm JSV, ale jest to fpras. Myśląc o innych pracach w ramach wygładzonej złożoności, silną wskazówką bycia w wygładzonym P było istnienie algorytmu …
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.