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...
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:...
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...
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ą...
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...
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....
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ć...
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ń...
Jakie są przykłady par klas złożoności i , żeAAABBB nie wiemy, czy , iA=BA=BA=B nie znamy też sprzecznych relatywizacji (tzn. nie znamy wyroczni i tak że i )?PPPQQQAP=BP.AP=BP.A^P = B^PZAQ≠BQAQ≠BQA^Q \ne B^Q Aby sformułować pytanie w inny sposób, jakie są wyjątki od heurystyki, że jeśli nie uda...
Czy NP jest w DTIME(npolylogn)DTIME(npolylogn)DTIME(n^{poly\log n})
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...
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...
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...
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...
Jakie są nietrywialne problemy, o których wiemy, że obecny algorytm jest asymptotycznie optymalny? (Do maszyn Turinga) Jak to
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,...
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...
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...
Krótkie pytanie Jaka jest moc obliczeniowa obwodów „kwantowych”, jeśli pozwolimy na niejednorodne (ale wciąż odwracalne) bramki i wymagamy, aby dane wyjściowe dawały prawidłową odpowiedź z pewnością? To pytanie w pewnym sensie dotyczy tego, co dzieje się z klasą kiedy pozwalasz obwodom na...
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,...