Niech zmiennymi będą . Odległość między dwiema zmiennymi jest zdefiniowana jako. Odległość między dwoma literałami jest odległością między odpowiednimi dwiema zmiennymi. d ( x a , x b ) = | a - b |x1, x2), x3). . . xnx1,x2,x3...xnx_1 , x_2 , x_3 ... x_nre( xza, xb) = | a - b |d(xa,xb)=|a−b|d(x_a ,...
Jeśli problem jest trudny dla NP (przy użyciu wielomianowych redukcji czasu), czy to oznacza, że jest trudny dla P (przy użyciu przestrzeni dziennika lub redukcji NC)? Wydaje się intuicyjne, że jeśli jest tak trudny jak jakikolwiek problem w NP, powinien być tak trudny jak jakikolwiek problem w...
wszyscy wiedzą, że istnieje wiele problemów decyzyjnych, które są trudne NP na ogólnych wykresach, ale interesują mnie problemy, które są trudne NP, gdy podstawowy wykres jest ścieżką. Czy możesz mi pomóc w zebraniu takich problemów? Znalazłem już powiązane pytanie dotyczące trudnych NP problemów...
W tym wątku próba próby Norbet Bluma jest zwięźle obalona przez odnotowanie, że funkcja Tardos jest przeciwne do Twierdzenia 6.P.≠ N.P.P≠NPP \neq NP Twierdzenie 6 : Niech będzie dowolną monotoniczną funkcją boolowską. Załóżmy, że istnieje aproksymator A CNF-DNF, którego można użyć do udowodnienia...
Rozważam klasy grafów, które można scharakteryzować za pomocą zabronionych subgrafów. Jeśli klasa grafów ma skończony zestaw zabronionych podgraphów, wówczas istnieje trywialny algorytm wielomianowego rozpoznawania czasu (można po prostu użyć brutalnej siły). Ale nieskończona rodzina zakazanych...
Wykresy sześcienne to wykresy, w których każdy wierzchołek ma stopień 3. Zostały one szeroko zbadane i jestem świadomy, że kilka problemów trudnych dla NP pozostaje trudnych dla NP nawet ograniczonych do podklas grafów sześciennych, ale niektóre inne stają się łatwiejsze. Nadklasą wykresów...
Wiele problemów związanych z grafem algorytmicznym można rozwiązać w czasie wielomianowym zarówno na wykresach nieważonych, jak i ważonych. Niektóre przykłady to najkrótsza ścieżka, min. Drzewo rozpinające, najdłuższa ścieżka (w ukierunkowanych grafach acyklicznych), maksymalny przepływ, min....
Jest to zgodne z „ Algorytmami z książki ”. Chociaż redukcje są również algorytmami, pomyślałem, że wątpliwe jest, aby pomyśleć o redukcji w odpowiedzi na pytanie o algorytmy z książki. Stąd osobne zapytanie! Wszelkie redukcje są mile widziane. Zacznę od bardzo prostej redukcji od osłony...
Shor stwierdził w swoim komentarzu do odpowiedzi anonimowego łosia na to pytanie. Czy potrafisz określić sumę dwóch permutacji w czasie wielomianowym? , To jest -Complete do określenia różnicę dwóch permutacji. Niestety, nie widzę prostą redukcję od problemu sumy permutacji i warto mieć N P...
Zadałem już to pytanie jakiś czas temu na MathOverflow , ale zgodnie z moją najlepszą wiedzą jest ono nadal otwarte, więc zamieszczam je ponownie w nadziei, że ktoś o nim usłyszy. Opis problemu Niech , i będą trzema partycjami w niepustych częściach (oznaczonych przez , i ) zestawu { }. Znajdź...
Niedawno przeszedłem przez bolesną zabawę polegającą na nieformalnym wyjaśnianiu koncepcji złożoności obliczeniowej młodemu utalentowanemu samoukiem, programistowi, który nigdy wcześniej nie odbył formalnego kursu algorytmów ani złożoności. Nic dziwnego, że wiele pojęć początkowo wydawało się...
Zmotywowani odpowiedzią Shora związaną z różnymi pojęciami kompletności NP, szukam problemu, który jest NP-kompletny przy redukcjach P, ale nie jest znany jako NP-kompletny przy redukcjach Logspace (najlepiej przez długi czas). Ponadto, czy znalezienie redukcji Logspace między problemami...
Jaki jest związek między algorytmami DNA a klasami złożoności określonymi za pomocą maszyn Turinga? Czym są pomiary złożoności, takie jak czas i przestrzeń w algorytmach DNA? Czy można je wykorzystać do rozwiązania problemów związanych z NP-zupełnymi, takich jak TSP, których maszyny von Neumann nie...
Łańcuch dodatek jest ciągiem liczb naturalnych , gdzie x 1 = 1 , a każdy wskaźnik i ≥ 2 mamy x ı = x j + x k kilku wskaźników 1 ≤ j , k < i . Długość łańcucha addycji N ; docelowej sieci addycji x( x1, x2), … , Xn)(x1,x2,…,xn)(x_1, x_2, \dots, x_n)x1= 1x1=1x_1 = 1i ≥ 2i≥2i\ge 2xja= xjot+...
W tym pytaniu wydaje się, że zidentyfikowaliśmy naturalny problem, który jest zupełny NP przy redukcjach losowych, ale być może nie przy redukcjach deterministycznych (chociaż zależy to od tego, które niesprawdzone założenia teorii liczb są prawdziwe). Czy znane są inne problemy? Czy istnieją...
(To pytanie jest trochę „ankietą”). Aktualnie pracuję nad problemem, w którym próbuję podzielić krawędzie turnieju na dwa zestawy, z których oba są wymagane do spełnienia niektórych właściwości strukturalnych. Problem „czuje się” bardzo trudne, a ja w pełni się spodziewać, że będzie...
Załóżmy, że mamy macierz n na n. Czy można zmienić kolejność wierszy i kolumn, tak aby uzyskać matrycę górnego trójkąta? To pytanie jest motywowane tym problemem: Pozytywne uporządkowanie topologiczne Pierwotny problem decyzyjny jest co najmniej tak trudny jak ten, więc wynik kompletności NP...
W moich badaniach pojawił się ostatnio następujący interesujący problem: INSTANCJA: Wykres .G ( V, E)G(V,E)G(V, E) ROZWIĄZANIE: Zakończenie akordu nieparzystego cyklu nieparzystego, zdefiniowane jako nadzbiór zestawu krawędzi tak że skompletowany wykres ma właściwość polegającą na tym, że każda...
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ą...
Sprzężenie zwrotne Zestaw wierzchołków jest NP-kompletny dla ogólnych wykresów. Wiadomo, że jest NP-kompletny dla wykresów ograniczonych do stopnia 8 ze względu na redukcję z pokrycia wierzchołków. Artykuł w Wikipedii mówi, że jest on rozwiązany w czasie wielozakresowym dla grafów związanych ze...