Pytania otagowane jako np-complete

Pytania dotyczące najtrudniejszych problemów w NP, tj. Tych, które można rozwiązać w czasie wielomianowym za pomocą niedeterministycznych maszyn Turinga.

3
Czy jakiś skończony problem może występować w NP-Complete?
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 rozumiem. Sudoku są NP kompletne, jeśli się nie mylę. Problem …
13 np-complete  np 
1
Środowisko wykonawcze ogranicza się do algorytmów NP całkowitych problemów przy założeniu P ≠ NP
Załóżmy, że .P≠NPP≠NPP\neq NP Co możemy powiedzieć o granicach czasu działania wszystkich problemów związanych z NP-zupełnością? tj. jakie są najostrzejsze funkcje dla których możemy zagwarantować, że optymalny algorytm dla dowolnego problemu z NP zakończony będzie w czasie co najmniej i co najwyżej na wejściu o długości ? ω ( L …
2
Udowodnienie, że DOUBLE-SAT jest NP-zakończone
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{ has at least two satisfying assignments}\} Jak udowodnimy, że jest kompletny NP? Doceniony zostanie więcej niż jeden …
2
Czy można rozwiązać dowolny problem NP-Complete przy użyciu co najwyżej przestrzeni wielomianowej (ale przy użyciu czasu wykładniczego?)
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 ją ogólnie uogólnić na EXPTIME …
2
Dlaczego twierdzenie Schaefera nie dowodzi, że P = NP?
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 (ponieważ CSP …
2
Wykazać kompletność NP decydującej o satysfakcji monotonicznej formuły boolowskiej
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 monotoniczną funkcją logiczną. …
4
Czy złożoność problemów silnie NP-trudnych lub -kompletnych zmienia się, gdy ich dane wejściowe są kodowane w sposób jednoznaczny?
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 przykład słabo NP-kompletny problem …
1
Czy problem trudny dla NP może być średnio wielomianowy?
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 ) dla stałej k ?P.≠ …
2
Najdłuższy cykl zawarty w dwóch cyklach
Czy następujący problem NP-jest kompletny? (Zakładam, że tak). Wprowadź: niekierowany wykres, na którym zbiór zboczy może zostać rozłożony na dwa proste cykle rozłączne od krawędzi ( nie są one częścią danych wejściowych).k∈N,G=(V,E)k∈N,G=(V,E)k \in \mathbb{N},G=(V,E) Pytanie: Czy istnieje prosty cykl w o długości większej niż ?kGGGkkk Oczywiście problem dotyczy NP, a …
1
Niezależny zestaw na sześciennych grafach bez trójkątów
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 grafie bez trójkątów musi mieć dokładnie węzły. ŻADNA instancja nie ma …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.