Pytania otagowane jako reductions

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.

4
Bezpośrednia redukcja SAT do 3-SAT
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 zmniejszenie, które zawsze widziałem w podręcznikach, wygląda mniej więcej tak: Najpierw …
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 …
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 …
1
Ważność potęgowania w wielomianowym skrócie czasu
Zadałem to pytanie 10 dni temu na cs.stackexchange tutaj, ale nie miałem żadnej odpowiedzi. W bardzo słynnego papieru (w środowisku sieciowym), Wang i Crowcroft przedstawić kilka -completeness wyniki obliczeń ścieżki pod kilkoma dodatkami / multyplikatywnych ograniczeń. Pierwszy problem jest następujący:NPNP\mathsf{NP} Biorąc pod uwagę ukierunkowany wykres i dwie miary wagi w …
1
Jaka jest minimalna wymagana głębokość redukcji dla NP-twardości SAT?
Jak każdy wie, SAT jest kompletna dla wrt wielomian czasie wiele-jeden redukcje. Nadal jest kompletny z redukcjami wielokrotności A C 0 .NPNP\mathsf{NP}AC0AC0\mathsf{AC^0} Moje pytania brzmi: jaka jest minimalna wymagana głębokość redukcji? Bardziej formalnie, Co najmniej takie, że SAT jest redukcją N P- twardą wr A C 0 d wielokrotności jeden?reddN …
1
Wykrywanie relacji liczb całkowitych dla podzbioru sumy lub NPP?
Czy istnieje sposób na zakodowanie wystąpienia Sumy Podzbioru lub Problemu Podziału Liczby, aby (małe) rozwiązanie relacji liczb całkowitych dało odpowiedź? Jeśli nie zdecydowanie, to w pewnym sensie probabilistycznym? Wiem, że LLL (i być może PSLQ) zostały zastosowane z umiarkowanym sukcesem w rozwiązywaniu problemów sumy częściowej w regionie „niskiej gęstości”, w …
5
Czy redukcje powinny nas bardziej lub mniej optymistycznie podchodzić do rozwiązania problemu?
Wydaje mi się, że większość teoretyków złożoności ogólnie uważa następującą zasadę filozoficzną: Jeśli nie możemy wymyślić skuteczny algorytm dla problemu i możemy zmniejszyć problemu A do problemu B , wtedy prawdopodobnie nie jest skuteczny algorytm dla problemu B , albo.ZAAAZAAAbBBbBB Dlatego, na przykład, gdy nowy problem zostanie udowodnione, NP-complete po …
1
Najwolniejsza redukcja wielokrotna?
Gdy chcemy udowodnić, że jest N P -Complete, to standardowe podejście jest wykazują czasie wielomianowym obliczalny wiele-jeden redukcji znanego N P -Complete problemu do L . W tym kontekście nie potrzebujemy ścisłego ograniczenia czasu działania redukcji. Wystarczy mieć dowolne wiązanie wielomianowe, co może mieć bardzo wysoki stopień.L∈NPL∈NPL\in \bf NPNPNP\bf NPNPNP\bf …
3
Zestaw łuków ze sprzężeniem zwrotnym (TFAS): NP-complete?
Jakiś czas temu wysłałem prośbę o referencję dotyczącą problemów z grafem, w której chcemy znaleźć 2-partycję krawędzi, w której oba zestawy spełniają właściwość niezwiązaną z ich licznością. Próbowałem udowodnić, że następujący problem jest NP-trudny: Biorąc pod uwagę turniej , czy istnieje zestaw sprzężeń zwrotnych F ⊆ E w G, który …
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.