Czy udowodniono, że obliczenia kwantowe nie są lepsze w rozwiązywaniu całkowitych problemów z NP niż obliczenia klasyczne, czy po prostu sądzi
Ponieważ całkowite programowanie liniowe jest zakończone NP, występuje zmniejszenie Karp z dowolnego problemu w NP. Pomyślałem, że to sugeruje, że zawsze istnieje wielomianowa formuła ILP dla dowolnego problemu w NP. Ale widziałem artykuły na temat konkretnych problemów związanych z NP, w których...
Planar 3SAT jest kompletny z NP. Płaska instancja 3SAT jest instancją 3SAT, dla której wykres zbudowany przy użyciu następujących reguł jest płaski: dodaj wierzchołek dla każdegoxixix_i i xi¯xi¯\bar{x_i} dodać wierzchołek dla każdej klauzuli CjCjC_j dodaj krawędź dla każdej pary...
Jeśli faktycznie jest równe N P , w jaki sposób poprawiłoby to nasze algorytmy do szybszego obliczania liczb całkowitych. Innymi słowy, jaki wgląd dałby nam ten fakt w lepszym zrozumieniu faktoryzacji liczb całkowitych?P.P.{\sf P}N P.NP.{\sf
Dobrze znany problem SAT został tu zdefiniowany dla odniesienia. Problem DOUBLE-SAT jest zdefiniowany jako DOUBLE-SAT={⟨ϕ⟩∣ϕ has at least two satisfying assignments}DOUBLE-SAT={⟨ϕ⟩∣ϕ has at least two satisfying assignments}\qquad \mathsf{DOUBLE\text{-}SAT} = \{\langle\phi\rangle \mid \phi \text{...
Problem 3 partycji zapytuje, czy zestaw liczb może być podzielona na n zestawy trzech liczb całkowitych takim, że każdy zestaw razem daje z danym całkowitą B . Problem zrównoważonej partycji pyta, czy 2 n liczb całkowitych można podzielić na dwa równe zestawy liczności, tak aby oba zestawy miały tę...
Mój wykładowca wydał oświadczenie Jakikolwiek problem skończony nie może być NP-Complete Mówił wtedy o Sudoku, mówiąc coś w stylu, że dla Sudoku 8x8 istnieje skończony zestaw rozwiązań, ale nie pamiętam dokładnie, co powiedział. Zapisałem notatkę, którą zacytowałem, ale nadal nie...
Załóżmy, że na uniwersytecie jest sesja szkoleniowa. Mamy zestaw pytań i zestaw studentów . Każdy uczeń ma wątpliwości w pewnym podzbiorze pytań, tj. Dla każdego ucznia , niech będzie zbiorem pytań, w które uczeń ma wątpliwości. Załóżmy, że i .kkkQ={q1…qk}Q={q1…qk}Q = \{ q_1 \ldots q_k...
Czytam o NPC i jego związku z PSPACE i chcę wiedzieć, czy problemy NPC można rozwiązać w sposób deterministyczny za pomocą algorytmu o najgorszym przypadku wymaganej przestrzeni wielomianowej, ale potencjalnie zajmującego wykładniczy czas (2 ^ P (n), gdzie P jest wielomianem). Co więcej, czy można...
Jeśli chodzi o najgorszy przypadek asymptotycznego środowiska uruchomieniowego, który problem NP-zupełny ma najszybszy znany (dokładny) algorytm i jaki jest algorytm? Czy jest coś znanego, co jest szybsze niż ?O ( n2)∗
Próbuję rozwiązać ten problem i naprawdę walczę. Monotoniczne logiczna wzór jest wzorem w zdań logiki, gdy wszystkie literałami dodatnie. Na przykład, ( x1∨ x2)) ∧ ( x1∨ x3)) ∧ ( x3)∨ x4∨ x5)(x1∨x2)∧(x1∨x3)∧(x3∨x4∨x5)\qquad (x_1 \lor x_2) \land (x_1 \lor x_3) \land (x_3 \lor x_4 \lor x_5) jest...
Zakładając, że mamy problem i pokazaliśmy, że dolną granicą rozwiązania jest .ppppppΩ(2n)Ω(2n)\mathcal{\Omega}(2^n) czy dolna granica oznacza problem w
Wiem więc, że sprawdzenie, czy zwykły język jest podzbiorem zwykłego języka jest rozstrzygalne, ponieważ możemy przekonwertować je oba na DFA, obliczyć , a następnie sprawdzić, czy ten język jest pusty.S R ∩ ˉ S.RRRS.S.SR ∩ S¯R∩S.¯R \cap \bar{S} Ponieważ jednak wymaga to konwersji do DFA, możliwe...
To chyba głupie pytanie, ale po prostu nie rozumiem. W kolejnym pytaniu wymyślili dychotomia twierdzenia Schaefer jest . Dla mnie wygląda na to, że udowadnia, że każdy problem CSP jest w P lub NP-kompletny, ale nie pomiędzy. Skoro każdy problem NP można przekształcić w czasie wielomianowym w CSP...
Czy trudność silnie trudnego NP lub problemu NP-zupełnego (jak np. Zdefiniowano tutaj ) zmienia się, gdy jego wejście jest jednoargumentowe zamiast kodowane binarnie? Jaką różnicę ma to, że wejście problemu silnie trudnego NP jest zakodowane w sposób jednoznaczny? Chodzi mi o to, że jeśli wezmę na...
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...
Zastanawiam się, czy są jakieś problemy twarde typu , które w przeciętnym przypadku są `` wielomianowe ''. Sądzę, że istnieją dwa sposoby interpretacji tego?N.P.N.P.NP Jeśli , czy może istnieć algorytm rozwiązujący problem twardości N P z zamortyzowanym (przypadkiem średnim) czasem pracy O ( n k...
Czy są znane algorytmy, które poprawnie wypisują odpowiedź „tak” dla problemu NP-complete bez pośredniego generowania certyfikatu? Rozumiem, że łatwo jest przekształcić wyrocznię spełniającą w znajdującą satysfakcjonujące zadanie: po prostu iteruj po zmiennych, za każdym razem pytając wyrocznię...
W pracy miałem za zadanie wnioskować o pewnych typach informacji o dynamicznym języku. Przepisuję sekwencje instrukcji na letwyrażenia zagnieżdżone , tak jak poniżej: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then { T;...
Zastanawiam się, czy istnieje algorytm wielomianowy dla „2-SAT z relacjami XOR”. Zarówno 2-SAT, jak i XOR-SAT są w P, ale czy jest to kombinacja? Przykładowe dane wejściowe: Część 2-SAT: (a or !b) and (b or c) and (b or d) Część XOR: (a xor b xor c xor 1) and (b xor c xor d) Innymi słowy,...