Pytania otagowane jako np-hardness

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

2
Kiedy „X jest kompletne NP” oznacza, że ​​„# X jest kompletne P”?
Niech oznacza problem (decyzji) w NP, a # oznacza jego wersję zliczającą.XXXXXXX Pod jakimi warunkami wiadomo, że „X to NP-zupełny” że „X jest kompletny?⟹⟹\implies Oczywiście istnienie skąpej redukcji jest jednym z takich warunków, ale jest to oczywiste i jedyny taki warunek, o którym wiem. Ostatecznym celem byłoby wykazanie, że żaden …
2
Czy potrafisz określić sumę dwóch permutacji w czasie wielomianowym?
Były dwa pytania zadawane niedawno na cs.se które były albo spokrewnione lub miał szczególny przypadek równoznaczne z następującym pytaniem: Załóżmy, że masz ciąg a1,a2,…ana1,a2,…ana_1, a_2, \ldots a_n z nnn liczb takich, że Rozłóż go na sumę dwóch permutacji, i , z , tak aby∑ni=1ai=n(n+1).∑i=1nai=n(n+1).\sum_{i=1}^n a_i = n(n+1).ππ\piσσ\sigma1…n1…n1 \dots nai=πi+σiai=πi+σia_i = …
1
Funkcje, które nie są wydajnie obliczalne, ale można się ich nauczyć
Wiemy, że (patrz np. Twierdzenia 1 i 3 z [1]), z grubsza mówiąc, w odpowiednich warunkach, funkcje, które mogą być skutecznie obliczone przez maszynę Turinga w czasie wielomianowym („wydajnie obliczalne”), mogą być wyrażone przez wielomianowe sieci neuronowe z rozsądnymi rozmiarami, a zatem można się go nauczyć z wielomianową złożonością próbki …
3
Czy „Gdzie są naprawdę trudne problemy”? Jakie są aktualne pomysły na ten temat?
Uważam ten artykuł za bardzo interesujący. Podsumowując: omawia, dlaczego w praktyce rzadko znajduje się najgorszy przypadek problemu NP-zupełnego. Idea tego artykułu polega na tym, że przypadki są zwykle bardzo niedostatecznie lub bardzo przeciążone, a oba są stosunkowo łatwe do rozwiązania. Następnie proponuje dla kilku problemów miarę „ograniczenia”. Wydaje się, że …
3
Zdecyduj, czy jądro macierzy zawiera jakiś niezerowy wektor, którego wszystkie wpisy to -1, 0 lub 1
Biorąc pod uwagę mmm o nnn binarnego macierzy MMM (wartość wynosi 000 lub 111 ), problemem jest ustalenie, czy istnieje dwoma wektorami binarnymi v1≠v2v1≠v2v_1 \ne v_2 w taki sposób, Mv1=Mv2Mv1=Mv2Mv_1 = Mv_2 (wszystkie operacje wykonywane przez ZZ\mathbb{Z} ). Czy ten problem jest trudny NP? Widać to wyraźnie w NP, ponieważ …
2
Czy można sprawdzić, czy sekwencja istnieje w czasie wielomianowym w następującym problemie?
Przez jakiś czas myślałem o następującym problemie i nie znalazłem rozwiązania wielomianowego. Tylko brutalne źródło. Próbowałem też zredukować problem NP-Complete bez powodzenia. Oto problem : Masz posortowany zestaw {(A1,B1),(A2,B2),…,(An,Bn)}{(A1,B1),(A2,B2),…,(An,Bn)}\{(A_1, B_1), (A_2, B_2), \ldots, (A_n, B_n)\} par dodatnich liczb całkowitych. (Ai,Bi)&lt;(Aj,Bj)⇔Ai&lt;Aj∨(Ai=Aj∧Bi&lt;Bj)(Ai,Bi)&lt;(Aj,Bj)⇔Ai&lt;Aj∨(Ai=Aj∧Bi&lt;Bj)(A_i, B_i) < (A_j, B_j) \Leftrightarrow A_i < A_j \lor (A_i …
3
Czy NP jest trudny do prawidłowego grania w drafty międzynarodowe?
Czy następujący problem jest trudny NP? Biorąc pod uwagę konfigurację forum dla międzynarodowych projektów , znajdź jeden legalny ruch.n×nn×nn\times n Odpowiedni problem dla amerykańskich warcabów (inaczej angielskich wersji roboczych) można w prosty sposób rozwiązać w czasie wielomianowym. Istnieją trzy główne różnice między tymi dwiema grami.n×nn×nn\times n Pierwszą i najbardziej znaczącą …
4
Zakres ograniczonej liczności ograniczonej obejmuje: twardość aproksymacji
Rozważ problem minimalnego pokrycia zestawu z następującymi ograniczeniami: każdy zestaw zawiera co najwyżej kkk elementów, a każdy element wszechświata występuje w co najwyżej zestawach fff Na przykład: w przypadku k=4k=4k = 4 i f=2f=2f = 2 odpowiada minimalnej wierzchołek problemu pokrywy na wykresach z maksymalnym stopniem 4. Niech a(k,f)&gt;1a(k,f)&gt;1a(k,f) > …
5
Weryfikacja unikalnych rozwiązań SAT
Rozważ następujący problem: biorąc pod uwagę formułę CNF i zadanie spełniające tę formułę, czy istnieje inne zadowalające przypisanie dla tej formuły? Jaka jest złożoność tego problemu? (Z pewnością jest w NP, ale czy to jest NP-trudne?) Co się stanie, jeśli nie otrzymasz zadania i chcesz po prostu zdecydować, czy formuła …
3
Twardość aproksymacji - błąd addytywny
Istnieje bogata literatura i co najmniej jedna bardzo dobra książka określająca znaną twardość wyników przybliżenia dla problemów trudnych dla NP w kontekście błędu multiplikatywnego (np. 2-przybliżenie dla pokrywy wierzchołków jest optymalne przy założeniu UGC). Obejmuje to również dobrze zrozumiałe klasy złożoności aproksymacji, takie jak APX, PTAS i tak dalej. Co …
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.