Czy następujący problem występuje w trybie PTIME lub coNP-hard: Biorąc pod uwagę dwa wyrażenia logiczne i w zmiennyche1e1e_1e2e2e_2 , bez negacji (tzn. Wyrażenia są w całości budowane przez ∧ i ∨ ). Zdecyduj, czy e 1 ≡ e 2 , czyli mają taką samą wartość dla wszystkich przypisań do...
Powiązany problem: Twierdzenie Veblena stwierdza, że „Wykres dopuszcza rozkład cyklu wtedy i tylko wtedy, gdy jest on parzysty”. Cykle są rozłączne na krawędziach, ale niekoniecznie są rozłączne w węzłach. Innymi słowy: „Zestaw krawędzi wykresu można podzielić na cykle, jeśli i tylko wtedy, gdy...
ΣP2Σ2P\mathsf{\Sigma^P_2}PP\mathsf{P} na ograniczonych wykresach szerokości drzewa. W rzeczywistości myślę, że te problemy są trudniejsze niż użycie normalnego programowania dynamicznego na wykresach ograniczonej szerokości do ich
Jaka jest minimalna liczba bramek binarnych potrzebnych do jednoczesnego obliczenia AND i OR bitów wejściowych? Trywialna górna granica wynosi 2 n - 2 . Uważam, że jest to optymalne, ale jak to udowodnić? Nie działa tutaj standardowa technika eliminacji bramki, ponieważ poprzez przypisanie stałej...
Według klasycznego wyniku Kurody, klasa złożoności NSPACE [ ]nnn (znana również jako NLIN-SPACE) jest właśnie klasą CSL języków kontekstowych . Problem satysfakcji SAT występuje w NSPACE [ ], ponieważ domysły o liniowym rozmiarze dla rozwiązania można sprawdzić z co najwyżej liniowym obciążeniem...
Jestem zainteresowany tym problemem: Biorąc pod uwagę undirected wykres , Czy istnieje podział na wykresach i takie, że i są izomorficzne?G(E,V)G(E,V)G(E, V)GGGG1(E1,V1)G1(E1,V1)G_1(E_1, V_1)G2(E2,V2)G2(E2,V2)G_2(E_2, V_2)G1G1G_1G2G2G_2 Tutaj jest podzielony na dwa rozłączne zestawy i . Zestawy i...
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ń...
Nie wiadomo, czy izomorfizm wykres (GI) do silnie graf regularny (SRGs) jest P . Czy są jakieś wskazówki, że może, ale nie musi, być GI -Complete? Czy w takich przypadkach są jakieś poważne konsekwencje? (Podobne do przekonania, że oznaczenie geograficzne może nie być
W zadaniu pakowania prostokąt, jeden dany zestaw prostokątów i prostokąt, R . Zadaniem jest znalezienie umieszczenie R 1 , ... , r n wewnątrz R takie, że żaden z n prostokąty pokrywają. Ogólnie, orientacja każdego prostokąta r i jest stała. Oznacza to, że prostokąty nie mogą być obracane. W tym...
Załóżmy, że dla każdego istnieje maszyna Turinga M ϵ, która decyduje o języku L w czasie O ( n a + ϵ ) . Czy istnieje jeden algorytm decydujący o L w czasie O ( n a + o ( 1 ) ) ? (Tutaj składnik o ( 1 ) jest mierzony jako n , długość wejściowa.)ϵ>0ϵ>0\epsilon >...
Nie mam wiedzy w zakresie teorii złożoności z udziałem grup, więc przepraszam, jeśli jest to dobrze znany wynik. Pytanie 1. Niech będzie prostym nieukierowanym grafem rzędu . Jaka jest złożoność obliczeniowa (w kategoriach ) ustalania, czy jest przechodnie dla
Załóżmy, że . N P ja to klasa problemów w N P , które nie są ani w P ani w N P -hard. Listę problemów, które można przypuszczać, że są N P I tutaj .P≠NPP≠NP\mathsf{P} \neq \mathsf{NP}NPINPI\mathsf{NPI}NPNP\mathsf{NP}PP\mathsf{P}NPNP\mathsf{NP}NPINPI\mathsf{NPI} Twierdzenie Ladnera mówi nam, że...
n×nn×nn\times nlog2(n)log2(n)\log^2(n)111∥A∥≤1‖A‖≤1\left\|A\right\|\leq 11/poly1/poly1/\text{poly} W związku z tym, o jakie „poprawne” przybliżenie należy zapytać - multiplikatywne lub addytywne? (patrz jedna z odpowiedzi
Ukazał się nowy artykuł, w którym twierdzono, że quasi-wielomianowy algorytm jest logarytmem dyskretnym. http://arxiv.org/abs/1306.4244 Jeśli jest poprawny, czy oznacza to, że nie mamy już wykładniczej separacji złożoności klasycznego algorytmu i jego wersji kwantowej dla problemu logarytmu...
Jest tylko bardzo mało informacji na temat kompletnego NP rozwiązania problemu liniowego równania diofantyny w liczbach całkowitych nieujemnych. To znaczy, czy jest to rozwiązanie w nieujemne x1,x2,...,xnx1,x2,...,xnx_1,x_2, ... , x_n do równania , gdzie wszystkie stałe są dodatnie? Jedyną godną...
Gowers przedstawił ostatnio problem, który nazywa „dyskretną determinacją Borela”, którego rozwiązanie dotyczy dolnych granic obwodu dowodzenia. Czy możesz podać podsumowanie podejścia, które jest dostosowane do grupy teoretyków złożoności? Co potrzeba, aby to podejście wykazało cokolwiek , w tym...
Jednoznaczne automaty skończone (UFA) są specjalnym typem niedeterministycznych automatów skończonych (NFA). NFA jest nazywany jednoznacznym, jeśli każde słowo ma co najwyżej jedną ścieżkę akceptującą.w ∈ Σ∗w∈Σ∗w\in \Sigma^* Oznacza to, .D F.A ⊂ UfaA ⊂ NfaZArefaZA⊂UfaZA⊂N.faZADFA\subset...
Szukam problemów, które są znane jako NPC dla grafów kierowanych, ale mają algorytm wielomianowy dla grafów bezkierunkowych. Widziałem pytanie dotyczące odwrotnych problemów, które są łatwiejsze niż ich „niekierowany” wariant , ale szukam twardości po stronie ukierunkowanej. Na przykład, zestaw...
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...
Czy NP jest w DTIME(npolylogn)DTIME(npolylogn)DTIME(n^{poly\log n})