Zadałem to pytanie 10 dni temu na cs.stackexchange tutaj, ale nie miałem żadnej odpowiedzi. W bardzo słynnego papieru (w środowisku sieciowym), Wang i Crowcroft przedstawić kilka -completeness wyniki obliczeń ścieżki pod kilkoma dodatkami / multyplikatywnych ograniczeń. Pierwszy problem jest...
Jakiś czas temu zadałem to pytanie na temat Przepełnienia stosu: Problem: sprzedaż Boba . Ktoś zasugerował także opublikowanie pytania tutaj. Ktoś już zadał tutaj pytanie związane z tym problemem - minimalna waga lasów danej liczności - ale o ile rozumiem, nie pomaga mi to z moim problemem. Warto...
Zestaw uderzenia z rodziny S.= { S1, … , Sn}S.={S.1,…,S.n}\mathcal{S} = \{S_1, \dots, S_n\} jest podzbiorem z taki sposób, do . Problem znalezienia minimalnego zestawu uderzeń z danej rodziny jest ogólnie trudny do przeprowadzenia, ponieważ uogólnia problem pokrycia wierzchołków. Teraz moje pytanie...
Miałem nadzieję, że ktoś może mi wyjaśnić, dlaczego dokładnie problem produktu z podzbiorem jest silnie trudny do NP, podczas gdy problem sumy z podzbiorem jest trudny do NP. Podzbiór Suma: Biorąc pod uwagę, i T , czy istnieje podzbiór X ' , tak że Σ i ∈ X ' x I = T .X={x1,...,xn}X={x1,...,xn}X =...
To pytanie jest ściśle związane z innym postem: Przejścia fazowe w trudnych problemach NP, ale jest nieco inne. Chociaż pytanie dotyczy twardości poszczególnych przypadków trudnych problemów NP, chodzi o uszeregowanie trudności tych samych przypadków. Istnieje wiele bibliografii na temat efektu...
Mam politotop P.PP zdefiniowany przez { x : A x ≤ b , x ≥ 0 }{x:Ax≤b,x≥0}\{ x : Ax \leq b, x \geq 0\} . Pytanie: Z uwagi wierzchołek vvv z P.PP , czy istnieje algorytm wielomianowy czas równomiernie próbki od sąsiadów vvv na wykresie P.PP ? (Wielomian w wymiarze, liczba równań i reprezentacja bbb...
Jaka jest złożoność obliczeniowa następującego problemu: dane dwie złożone macierzy i sprawdzają, czy istnieje macierz permutacji taka, że: B P B = P P T .n × nn×nn\times nZAZAAbbBP.P.PB = PA P.T..b=P.ZAP.T..B = P A P^T. Jeśli to pomoże, można założyć, że i są pustelnikami (lub nawet, że i są...
Rozważmy zbiór zbiorów F = { F 1 , F 2 , … , F n } nad zestawem podstawowym U = { e 1 , e 2 , … , e n } gdzie | F i | « N i e i ∈ F I i pozwolić K jest dodatnią liczbą całkowitą.F={F1,F2,…,Fn}F=\{F_1,F_2,\dotsc,F_n\}U={e1,e2,…,en}U=\{e_1,e_2,\dotsc,e_n\}|Fi||F_i| ≪\ll nnei∈Fie_i \in F_ikk Celem...
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...
Problem: Biorąc pod uwagę reprezentowane przez obwód logiczny, wygeneruj równomiernie losowy x ∈ { 0 , 1 } n taki, że ϕ ( x ) = 1 (lub wyjście ⊥, jeśli nie ma takiego x istnieje). ϕ : { 0 , 1 }n→ { 0 , 1 }ϕ:{0,1}n→{0,1}\phi : \{0,1\}^n \to \{0,1\}x ∈ { 0 , 1 }nx∈{0,1}nx \in \{0,1\}^nϕ ( x ) =...
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...
To nazwa, którą wymyśliłem dla tego problemu. Nigdzie go nie widziałem. Nie udało mi się znaleźć dowodu kompletności NP ani algorytmu wielomianowego czasu dla tego problemu. To nie jest zadanie domowe - jest związane z problemem, z którym się spotkałem w swojej pracy. NAJNOWSZE BITKI...
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 -> b seq ⊥ b =...
Niedawno czytałem bardzo fajny artykuł Valianta i Vazirani, który pokazuje, że jeśli , to nie może być skutecznego algorytmu do rozwiązania SAT, nawet pod obietnicą, że jest albo niezadowalający, albo ma unikalne rozwiązanie. W ten sposób pokazując, że SAT nie dopuszcza wydajnego algorytmu nawet...
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 = ( [ n ] , M ∪ H )...
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...
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...
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...
Oto problem: W niektórych komórkach mamy kwadrat z niektórymi liczbami od 1..N. Trzeba ustalić, czy można go ukończyć na magiczny kwadrat. Przykłady: 2 _ 6 2 7 6 _ 5 1 >>> 9 5 1 4 3 _ 4 3 8 7 _ _ 9 _ _ >>> NO SOLUTION 8 _ _ Czy ten problem NP-jest kompletny? Jeśli tak, jak...
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...