Redukcja polega na przekształceniu jednego problemu w inny. Przykładem zastosowania redukcji byłoby pokazanie, czy problem P jest nierozstrzygalny. Można to osiągnąć poprzez przekształcenie lub wykonanie redukcji problemu decyzyjnego w problem nierozstrzygalny. Jeśli można to osiągnąć, wykazaliśmy, że problem P jest nierozstrzygalny. P. P.
Dlaczego większość ludzi woli stosować redukcje wielokrotne jeden do zdefiniowania kompletności NP zamiast, na przykład, redukcji
Suma pierwiastki problemu prosi, ponieważ dwie sekwencje i dodatnich liczb całkowitych czy suma mniejszy, równy lub większy niż suma . Status złożoności tego problemu jest otwarty; zobacz ten post, aby uzyskać więcej informacji. Problem ten powstaje naturalnie w geometrii obliczeniowej, szczególnie...
Przypuszcza się, że losowość nie rozszerza potęgi algorytmów wielomianu czasowego, co oznacza, że jest przypuszczalny do utrzymania. Z drugiej strony losowość wydaje się mieć zupełnie inny wpływ na skrócenie czasu wielomianu . Według dobrze znanego wyniku Valiant i Vazirani, redukuje się do poprzez...
Twierdzenie Valiant-Vazirani mówi, że jeśli istnieje wielomianowy algorytm czasu (deterministyczny lub losowy) do rozróżniania między formułą SAT, która ma dokładnie jedno zadowalające przypisanie, a formułą niezadowalającą - wówczas NP = RP . Twierdzenie to zostało udowodnione poprzez wykazanie,...
Wpis na blogu Scotta Aaronsona przedstawił dziś listę interesujących otwartych problemów / zadań w złożoności. Jeden zwrócił moją uwagę: Zbuduj bibliotekę publiczną instancji 3SAT z jak najmniejszą liczbą zmiennych i klauzul, które mogłyby mieć godne uwagi konsekwencje, jeśli zostaną rozwiązane....
Czy jest przykładem języka, który jest w NPNPNP , ale gdzie nie możemy udowodnić ten fakt bezpośrednio poprzez pokazanie, że istnieje wielomian świadka do członkostwa w tym języku? Zamiast tego fakt, że język znajduje się w NPNPNP , można udowodnić, redukując go do innego języka w NPNPNP , gdzie...
Niektóre problemy trudne NP, które są wykładnicze na grafach ogólnych, są sub wykładnicze na grafach płaskich, ponieważ szerokość wynosi co najwyżej i są wykładnicze w szerokości.4,9 | V.( G ) |------√4.9|V(G)|4.9 \sqrt{|V(G)|} Zasadniczo jestem zainteresowany, czy istnieją algorytmy...
Zliczanie liczby idealnych dopasowań na wykresie dwustronnym można natychmiast zredukować do obliczenia wartości stałej. Ponieważ znalezienie idealnego dopasowania na grafie dwustronnym występuje w NP, istnieje pewna redukcja z grafów dwustronnych do stałych, ale może to wiązać się z nieprzyjemnym...
Widoczna jest redukcja z CLIQUE na k-Color, ponieważ oba są NP-Complete. W rzeczywistości mogę go zbudować, tworząc redukcję z CLIQUE do 3-SAT z redukcją z 3-SAT do k-Color. Zastanawiam się, czy istnieje rozsądna bezpośrednia redukcja między tymi problemami. Powiedzmy, redukcję, którą mógłbym...
Niektórzy z was mogli śledzić to pytanie , które zostało zamknięte z powodu braku poziomu badań. Wyciągam więc część pytania, która jest na poziomie badawczym. Oprócz „prostszych” technik, takich jak redukcja do sortowania lub problem z WYŁĄCZENIEM, jakie techniki zostały zastosowane, aby...
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...
To pytanie dotyczy związku między normalnym mnożeniem liczb binarnych a wielomianowym mnożeniem mod 2. Aby uczynić pytanie konkretnym, idealnie chciałbym wiedzieć, czy istnieje lepsze rozwiązanie pytania z Knuth vol. 2, wydanie trzecie, strona 420 niż podano w książce. „Czy mnożenie wielomianów...
W artykule „KOMPLEKSOWOŚĆ PROBLEMÓW Z ZADOWOLENIEM” Tomasza J. Schaefera autor wspomniał, że This raises the intriguing possibility of computer-assisted NP-completeness proofs. Once the researcher has established the basic framework for simulating conjunctions of clauses, the relational complexity...
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ą...
USTCONN to problem, który wymaga podjęcia decyzji, czy istnieje ścieżka od wierzchołka źródłowego sss do wierzchołka docelowego ttt na wykresie GGG , gdzie wszystkie są podane jako część danych wejściowych. Omer Reingold wykazał, że USTCONN znajduje się w L (doi: 10.1145 / 1391289.1391291 ). Dowód...
Tutaj celem jest zredukowanie arbitralnego problemu SAT do 3-SAT w czasie wielomianowym przy użyciu jak najmniejszej liczby klauzul i zmiennych. Moje pytanie jest motywowane ciekawością. Mniej formalnie chciałbym wiedzieć: „Jaka jest„ najbardziej naturalna ”redukcja z SAT na 3-SAT?” Teraz...
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...
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...
Jak wszyscy wiedzą, słynna książka Garey i Johnsona (i wiele innych) stanowi doskonałe odniesienie do techniki redukcji w scenerii klasycznej. Czy są jakieś ankiety lub książki na temat techniki redukcji w sparametryzowanym algorytmie, powiedzmy redukcja
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 =...