Pytania otagowane jako np-hardness

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

2
Czy znane są problemy NP-zupełne, ani trudne NP w silnym znaczeniu, ani algorytm pseudopolinomalny?
W swoim artykule (s. 503) Garey i Johnson zauważają: ... może istnieć problem NP-zupełny, który nie jest ani NP-zupełny w sensie silnym, ani rozwiązany przez algorytm pseudo-wielomianowy ... Czy ktoś zna problemy z kandydatami dotyczące wyżej wymienionych właściwości? Myślę, że możliwą odpowiedzią na to pytanie może być lista problemów NP-zupełnych …
2
Co-NP-kompletność minimalnej trasy TSP?
Ten problem pojawił się w moim niedawnym poście na blogu , przypuśćmy, że masz wycieczkę po TSP, czy jest to zgodne z NP-kompletnym, aby ustalić, czy jest to minimalne? Dokładniej jest następujący problem NP-zupełny: Instancja: Biorąc pod uwagę pełny wykres G z krawędziami ważonymi dodatnimi liczbami całkowitymi i prosty cykl …
2
Motywację do stosowania Karp-redukcji w teorii
Pojęcie wielomianowych redukcji czasu (redukcje Cooka) jest abstrakcją bardzo intuicyjnej koncepcji: skutecznego rozwiązywania problemu za pomocą algorytmu dla innego problemu. Jednakże, w teorii -completeness pojęcie -hardness jest rejestrowany za pomocą redukcji odwzorowania (redukcje Karp). Ta koncepcja „ograniczonych” redukcji jest o wiele mniej intuicyjna (przynajmniej dla mnie). Wydaje się nawet nieco …
1
Złożoność problemu pokrycia interwałów
Rozważmy następujący problemQQQ : Otrzymujemy liczbę całkowitą i przedziałów z . także liczb całkowitych . Zadanie polega na wybraniu minimalnej liczby przedziałównnnkkk[li,ri][li,ri][l_i,r_i]1≤li≤ri≤2n1≤li≤ri≤2n1\leq l_i\leq r_i\leq 2n2n2n2nd1,…,d2n≥0d1,…,d2n≥0d_1,…,d_{2n}\geq 0 , że dla każdego i = 1 , ... , 2 n , co najmniej d ı odstępach zawierających całkowitą i są zaznaczone.[li,ri][li,ri][l_i,r_i]i=1,…,2ni=1,…,2ni=1,…,2ndidid_iiii Nietrudno …
1
Jaka jest złożoność tego problemu kolorowania krawędzi?
Ostatnio spotkałem następujący wariant kolorowania krawędzi. Biorąc pod uwagę połączony niekierowany wykres, znajdź kolorystykę krawędzi, która wykorzystuje maksymalną liczbę kolorów, jednocześnie spełniając ograniczenie, że dla każdego wierzchołka krawędzie padające na v używają co najwyżej dwóch kolorów.vvvvvv Po pierwsze sądzę, że problem jest trudny do rozwiązania. Klasyczne twarde proofy NP na …
2
Czy naprawdę można wykazać silną twardość NP za pomocą zwykłych redukcji czasu politytime?
Niedawno przeczytałem dowód, który miał wykazać, że problem był silnie NP-trudny, po prostu redukując go (w czasie wielomianowym) z problemu silnie NP-trudnego. To nie miało dla mnie żadnego sensu. Pomyślałbym, że musisz pokazać, że wszelkie liczby użyte w redukcji i przypadki problemu, do którego redukujesz, są wielomianowo ograniczone w wielkości …
4
Złożoność znalezienia drugiego rozwiązania przy poprawnym rozwiązaniu problemu NP-zupełnego
Chcę dowiedzieć się, czy istnieją jakieś ogólne wyniki lub przykłady dotyczące kompletności NP problemu znalezienia drugiego rozwiązania problemu NP-zupełnego. Dokładniej, jestem zainteresowany wszelkimi problemami następującej formy: Biorąc pod uwagę rozwiązanie na przykład I z NP-pełnej problemem jest to, że roztwór S ' ≠ S do I ?SSSIjaIS′≠SS′≠SS' \neq SIII Docenione …
2
Problem cięcia bez H
Załóżmy, że otrzymałeś połączony, prosty, niekierowany wykres H. Problem cięcia bez H jest zdefiniowany następująco: Biorąc pod uwagę prosty, nieukierowany wykres G, istnieje cięcie (podział wierzchołków na dwa niepuste zbiory, L, R), tak że oba wykresy indukowane przez zestawy cięcia (L i R) nie zawierają izomorficznego subgrafu do H . …
1
Mieszanie hasła przy użyciu NP pełne problemy
Powszechnie używane algorytmy haszujące hasła działają dzisiaj tak: Zasol hasło i wprowadź je do KDF. Na przykład przy użyciu PBKDF2-HMAC-SHA1 proces mieszania hasła toDK = PBKDF2(HMAC, Password, Salt, ...) . Ponieważ HMAC jest 2-okrągłym skrótem z wyściełanymi klawiszami, a SHA1 szereg permutacji, przesunięć, rotacji i operacji bitowych, zasadniczo cały proces …
1
Jaka jest złożoność tego problemu z grafem?
Biorąc pod uwagę prosty niekierowany wykres GGG , znajdź podzbiór A≠∅A≠∅A\neq \emptyset wierzchołków, taki jak dla dowolnego wierzchołka x∈Ax∈Ax\in A co najmniej połowa sąsiadów xxx również znajduje się w AAA i rozmiar AAA jest minimalny. Oznacza to, że szukamy gromady, w której co najmniej połowa sąsiedztwa każdego wewnętrznego wierzchołka pozostaje …
2
Czy przecięcie matroidów graficznych
Wiadomo, że przecięcie trzech ogólnych matroidów jest NP-twarde ( źródło ), co odbywa się poprzez redukcję z cyklu Hamiltona. Redukcja wykorzystuje jedną matroidę graficzną i dwie matroidy łączności. Specjalny przypadek problemu, nad którym pracuję, można rozwiązać, przecinając wiele matroidów graficznych, ale nie udało mi się ustalić, czy problem występuje w …
4
Problemy z grafem, które są NP-Complete na grafach ukierunkowanych, ale wielomianowe na grafach niekierowanych
Szukam problemów, które są znane jako NPC dla grafów kierowanych, ale mają algorytm wielomianowy dla grafów bezkierunkowych. Widziałem pytanie dotyczące odwrotnych problemów, które są łatwiejsze niż ich „niekierowany” wariant , ale szukam twardości po stronie ukierunkowanej. Na przykład, zestaw krawędzi sprzężenia zwrotnego jest znany jako NPC na ukierunkowanych, ale wielomianowych …
2
Liniowe równanie diofantyny w liczbach całkowitych nieujemnych
Jest tylko bardzo mało informacji na temat kompletnego NP rozwiązania problemu liniowego równania diofantyny w liczbach całkowitych nieujemnych. To znaczy, czy jest to rozwiązanie w nieujemne x1,x2,...,xnx1,x2,...,xnx_1,x_2, ... , x_n do równania , gdzie wszystkie stałe są dodatnie? Jedyną godną uwagi wzmianką o tym problemie, który znam, jest Teoria programowania …
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.