Pytania otagowane jako np-hardness

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

2
Dokładne algorytmy czasu wykładniczego dla programów 0-1 z danymi nieujemnymi
Czy są znane algorytmy dla następującego problemu, które pokonały naiwny algorytm? Dane wejściowe: matryca AAA i wektory b,cb,cb,c, gdzie wszystkie wpisy z pozycji A,b,cA,b,cA,b,c są liczbami całkowitymi nieujemnymi. Wyjście: optymalne rozwiązanie x∗x∗x^* do max{cTx:Ax≤b,x∈{0,1}n}max{cTx:Ax≤b,x∈{0,1}n}\max \{ c^T x : Ax \le b, x \in \{ 0,1\}^n \}. To pytanie jest udoskonaloną …
3
Czy może istnieć wyjątkowo duży ukryty podzbiór problemów wielomianowo możliwych do rozwiązania w ramach problemów NP-Complete?
Załóżmy, że P! = NP. Wiemy, że w każdej chwili możemy wykonać proste instancje 3-SAT. Możemy również wygenerować coś, co uważamy za trudne wystąpienie (ponieważ nasze algorytmy nie potrafią ich szybko rozwiązać). Czy jest coś, co przeszkadza, by zbiór twardych instancji był arbitralnie mały, o ile dla dowolnej wielkości instancji …
1
Twardość NP specjalnego przypadku problemu upakowania ortogonalnego
Pozwolić VVV być zestawem DDD-wymiarowe kształty prostokątne. Dlad∈{1,...,D}d∈{1,...,D}d \in \{1,...,D\} i v∈Vv∈Vv \in V, wd(v)∈Q+wd(v)∈Q+w_d(v) \in \mathbb{Q}^{+} opisuje długość vvv w wymiarze ddd. Ta sama notacja jest używana dla konteneraCCC. TheDDD-wymiarowy problem pakowania ortogonalnego (OPP-DDD) ma zdecydować, czy VVV pasuje do pojemnika CCCbez nakładania się. Formalnie rzecz biorąc, problemem jest …
1
Czy problem tworzenia kopii zapasowej NP jest kompletny?
Czy następujący problem decyzyjny NP-zupełny: Niech będzie nieukierowanym wykresem i dwiema liczbami całkowitymi. Czy można wybrać dla każdego wierzchołka dokładnie różnych sąsiadów, tak że żaden węzeł nie zostanie wybrany więcej niż razy.GGGb≤cb≤cb \le cGGGbbbccc Przypadek można rozwiązać dla dowolnego czasie wielomianowym, stosując maksymalne dopasowanie.b=1b=1b = 1ccc Motywacja: każdy węzeł chce …
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.