Pytania otagowane jako np-hardness

Pytania dotyczące twardości NP i kompletności NP.

2
Dodaj dopasowanie do ścieżki hamiltonianu, aby zmniejszyć maksymalną odległość między podanymi parami wierzchołków
Jaka jest złożoność następującego problemu? Wejście : aścieżka hamiltonowskaw K nHH.HKnKnK_n podzbiór par wierzchołkówR⊆[n]2R⊆[n]2R \subseteq [n]^2 dodatnia liczba całkowita kkk Pytanie : czy istnieje pasujące , że dla każdego ( v , u ) ∈ R , d G ( v , u ) ≤ k ? (gdzie G = …
5
Dokładne algorytmy dla zestawu R-Dominującego na wykresach ograniczonej Treewidth
Biorąc pod uwagę wykres, G=(V,E)G=(V,E)G = (V, E) , to znaleźć optymalną rrr -domination dla GGG . Oznacza to, że chce podzbiór SSS o VVV tak, że wszystkie wierzchołki GGG znajdują się w odległości co najwyżej rrr z pewnym wierzchołka w SSS , przy jednoczesnym zminimalizowaniu rozmiaru .SSS Z tego, …
4
Czy eta-równoważność funkcji jest zgodna z sekwencją Haskella?
Lemat: Zakładając, że równoważność eta istnieje (\x -> ⊥) = ⊥ :: A -> B. Dowód: ⊥ = (\x -> ⊥ x)przez eta-równoważność i (\x -> ⊥ x) = (\x -> ⊥)redukcję pod lambda. Raport Haskell 2010, rozdział 6.2 określa seqfunkcję na podstawie dwóch równań: seq :: a -> b …
1
Jaka jest minimalna wymagana głębokość redukcji dla NP-twardości SAT?
Jak każdy wie, SAT jest kompletna dla wrt wielomian czasie wiele-jeden redukcje. Nadal jest kompletny z redukcjami wielokrotności A C 0 .NPNP\mathsf{NP}AC0AC0\mathsf{AC^0} Moje pytania brzmi: jaka jest minimalna wymagana głębokość redukcji? Bardziej formalnie, Co najmniej takie, że SAT jest redukcją N P- twardą wr A C 0 d wielokrotności jeden?reddN …
1
Jak problem może występować w NP, być trudnym NP, a nie kompletnym NP?
Najdłużej myślałem, że problem był NP-zupełny, jeśli jest zarówno (1) NP-trudny, jak i (2) jest w NP. Jednak w słynnym artykule „Metoda elipsoidy i jej konsekwencje w optymalizacji kombinatorycznej” autorzy twierdzą, że problem ułamkowej liczby chromatycznej należy do NP i jest trudny do NP, ale nie jest znany jako NP-zupełny. …
1
Wykrywanie relacji liczb całkowitych dla podzbioru sumy lub NPP?
Czy istnieje sposób na zakodowanie wystąpienia Sumy Podzbioru lub Problemu Podziału Liczby, aby (małe) rozwiązanie relacji liczb całkowitych dało odpowiedź? Jeśli nie zdecydowanie, to w pewnym sensie probabilistycznym? Wiem, że LLL (i być może PSLQ) zostały zastosowane z umiarkowanym sukcesem w rozwiązywaniu problemów sumy częściowej w regionie „niskiej gęstości”, w …
1
Czy istnieją ciekawe klasy grafów, w których obliczanie szerokości jest trudne (łatwe)?
Treewith jest ważnym parametrem grafu, który wskazuje, jak blisko wykres jest od drzewa (choć nie w ścisłym sensie topologicznym). Powszechnie wiadomo, że obliczenie szerokości jest trudne dla NP. Czy są jakieś naturalne klasy wykresów, w których trudno jest obliczyć szerokość ? Podobnie: Czy istnieją ciekawe klasy grafów, w których obliczanie …
4
Znalezienie najrzadszego rozwiązania układu równań liniowych
Jak trudno jest znaleźć najrzadsze rozwiązanie układu równań liniowych? Bardziej formalnie, rozważ następujący problem decyzyjny: Instancja: układ równań liniowych o współczynnikach całkowitych i liczbie ccc . Pytanie: Czy istnieje rozwiązanie dla systemu z co najmniej ccc zmiennymi przypisanymi do zera? Próbuję również ustalić, na czym polega zależność od ccc . …
2
Leksykograficznie minimalny rodzaj topologiczny oznaczonego DAG
Rozważmy problem, w którym jako dane wejściowe podajemy ukierunkowany wykres acykliczny , funkcję znakowania λ od V do jakiegoś zbioru L o całkowitej kolejności < L (np. Liczby całkowite) i gdzie jesteśmy proszeni o obliczyć leksykograficznie najmniejszy rodzaj topologiczny G pod względem λ . Dokładniej, A topologiczna sortowania z G …
1
Trudne problemy z rozszerzalnością
W przypadku problemu z rozszerzeniem otrzymujemy część rozwiązania i chcemy zdecydować, czy możemy go rozszerzyć do kompletnego rozwiązania. Niektóre problemy związane z rozszerzalnością można skutecznie rozwiązać, podczas gdy inne problemy z możliwością rozbudowy przekształcają problem łatwy w trudny. Na przykład twierdzenie Koniga-Halla stwierdza, że ​​wszystkie sześcienne dwustronne wykresy można pokolorować …
3
Zestaw łuków ze sprzężeniem zwrotnym (TFAS): NP-complete?
Jakiś czas temu wysłałem prośbę o referencję dotyczącą problemów z grafem, w której chcemy znaleźć 2-partycję krawędzi, w której oba zestawy spełniają właściwość niezwiązaną z ich licznością. Próbowałem udowodnić, że następujący problem jest NP-trudny: Biorąc pod uwagę turniej , czy istnieje zestaw sprzężeń zwrotnych F ⊆ E w G, który …
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.