Rozważ dołączony niekierowany wykres z nieujemnymi wagami krawędzi i dwoma wyróżnionymi wierzchołkami . Poniżej przedstawiono niektóre problemy ze ścieżką, które mają następującą postać: znajdź ścieżkę , tak aby jakaś funkcja ciężaru krawędzi na ścieżce była minimalna. W tym sensie wszyscy są...
W zoo o złożoności napisano [ 1 ], że w złożoności opisowej można zdefiniować za pomocą trzech różnych rodzajów wzorów, który jest również , a także jako .PPPFO(LFP)FO(LFP)FO(LFP)FO(nO(1))FO(nO(1))FO(n^{O(1)})SO(HORN)SO(HORN)SO(HORN) Istnieją jednak pewne wyjątki, na przykład nie może być wyrażona...
Twierdzenie Mahaneya mówi nam, że jeśli istnieje rzadki zestaw przy wielomianowych redukcjach wielokrotności jeden, to . (Patrz „ Rzadkie kompletne zestawy dla NP: Rozwiązanie przypuszczenia Bermana i Hartmanisa ”)NPNPNPP=NPP=NPP = NP Czy znane są konsekwencje istnienia rzadkich kompletnych...
Nie wiadomo czy P⊆CSLP⊆CSLP\subseteq CSL lub P⊈CSLP⊈CSLP\not\subseteq CSL, gdzie PPP jest zbiorem wszystkich języków rozstrzygalnych w czasie wielomianowym na deterministycznej maszynie Turinga, oraz CSLCSLCSL jest klasą języków kontekstowych, znanych jako równoważne...
Przepraszam, to trochę „miękkie” pytanie. Teoria informacji nie ma pojęcia złożoności obliczeniowej. Na przykład instancja SAT lub instancja SAT plus bit wskazujący na satysfakcję niosą tę samą ilość informacji. Czy istnieje sposób sformalizowania pojęcia „wielomianowo poznawalny”? Takie ramy...