Wiem, że maksymalny niezależny zestaw na sześciennych grafach bez trójkątów jest NP-zupełny. Czy nadal jest NP-kompletny, jeśli potrzebujemy, aby niezależny zestaw miał dokładnie taką samą wielkość ?| V.| / 2|V.|/2)|V|/2 Zasadniczo YES wystąpienie problemu z niezależnym zestawem na szesnastkowym...
Rozważ następujące stwierdzenie problemu: Biorąc pod uwagę początkową liczbę, ty i twój przyjaciel na zmianę odejmujemy od niej idealny kwadrat. Pierwszy, który osiągnie zero, wygrywa. Na przykład: Stan początkowy: 37 Gracz 1 odejmuje 16. Stan: 21 Gracz 2 odejmuje 8. Stan: 13 Gracz 1...
Pebbling to gra w pasjansa rozgrywana na niekierowanym grafie , gdzie każdy wierzchołek ma zero lub więcej kamyków. Pojedynczy ruch kamyka polega na usunięciu dwóch kamyków z wierzchołka v i dodaniu jednego kamyka do dowolnego sąsiada v . (Oczywiście, wierzchołek v musi mieć co najmniej dwa...
Moja książka to stwierdza Jeśli problem decyzyjny B występuje w P, a A zmniejsza się do B, to problem decyzyjny A występuje w P. Problem decyzyjny B jest NP-kompletny, jeśli B występuje w NP, a dla każdego problemu w A w NP A zmniejsza się do B. Problem decyzyjny C jest NP-kompletny, jeśli C...
Rozważ następujący problem, którego instancją wejściową jest prosty wykres i naturalna liczba całkowita k .solGGkkk Czy istnieje zestaw taki, że G - S jest dwustronny i | S | ≤ k ?S.⊆ V.( G )S⊆V(G)S \subseteq V(G)G - SG−SG - S| S.| ≤k|S|≤k|S| \leq k Chciałbym pokazują, że problem ten jest...
Mieliśmy kilka pytań na temat relacji redukcji Cooka i Karp . Oczywiste jest, że redukcje Cooka (redukcje Turinga w czasie wielomianowym) nie definiują tego samego pojęcia kompletności NP jak redukcje Karp (redukcje w postaci wielomianu w jednym czasie), które są zwykle stosowane. W szczególności...
Właściwie odkryłem, że zestaw języków kontekstowych, ( zaakceptowane języki) nie są tak szeroko omawiane, jak (zwykłe języki) lub (języki bezkontekstowe). A także problem otwarty nie jest tak znany jak problem „analogiczny”: „ ".C S LdoS.L.\mathbf{CSL}= N S P A C E ( O ( n ) ) = L B...
Alternatywne sformułowanie Wymyśliłem alternatywne sformułowanie do poniższego problemu. Alternatywne sformułowanie jest w rzeczywistości szczególnym przypadkiem poniżej problemu i wykorzystuje dwuczęściowe wykresy do opisania problemu. Uważam jednak, że alternatywny preparat jest nadal trudny do...
Biorąc pod uwagę liczb tak, że istnieje przypisanie liczb który jest permutacją taki, żeA 1 ≤ A 2 ≤ . . . ≤ A k k ∑kkkA1≤A2≤...≤AkA1≤A2≤...≤AkA_1 \leq A_2 \leq ... \leq A_k∑i=1kAi=k(2k+1)∑i=1kAi=k(2k+1)\sum\limits_{i=1}^k A_i = k(2k + 1)i1,i2,...,i2ki1,i2,...,i2ki_1, i_2, ... ,...
Mam w głowie problem, myślę, że jest to problem NPC, ale nie wiem, jak to udowodnić. Oto problem: Istnieje k wyspy w bardzo dużym jeziorem, a tam są n kształcie wachlarza pontony. Te pontony są tego samego rozmiaru, ale mają różne początkowe kierunki i znajdują się w różnych oryginalnych...
Istnieje klasyczna gra logiczna, bardzo podobna do krzyżówki, z tą różnicą, że podana jest lista słów, a następnie podana jest kwadratowa tablica złożona z kwadratów jednostkowych, z niektórymi kwadratami zaciemnionymi jak krzyżówka, a na niektórych kwadratach jest już napisany list. Celem jest...
Biorę kurs na złożoność obliczeniową. Mój problem polega na tym, że nie rozumiem metody relatywizacji . Próbowałem znaleźć odrobinę intuicji w wielu podręcznikach, jak dotąd niestety bez powodzenia. Będę wdzięczny, jeśli ktoś może rzucić światło na ten temat, abym mógł kontynuować sam. Kilka...
Biorąc pod uwagę (binarny) program liczbowy w postaci:0 , 10,10,1 minśwfa( x )A x = bxja≥ 0xja∈ { 0 , 1 }∀ i∀ iminf(x)s.t.Ax=bxi≥0∀ixi∈{0,1}∀i \begin{array}{lll} \text{min} & f(x) & \\ \text{s.t.} & A x = b \\ & x_i \ge 0 & \quad \forall i\\ & x_i \in \{0,1\} & \quad \forall...
Powiedzmy, że wiemy, że problem A jest trudny, a następnie redukujemy A do nieznanego problemu B, aby udowodnić, że B jest również trudny. Jako przykład: wiemy, że 3-kolorowanie jest trudne. Następnie redukujemy kolorowanie 3 do koloru 4. Po połączeniu jednego z kolorów 3-kolorowania masz...