Pytania otagowane jako np-hardness

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

5
Wystąpienie redukcji FPT, która nie jest redukcją czasu wielomianowego
W sparametryzowanej złożoności ludzie używają redukcji stałych parametrów (FPT), aby udowodnić twardość W [t]. Teoretycznie redukcja FPT nie jest redukcją czasu wielomianowego, ponieważ może działać wykładniczo w parametrze k. Ale w praktyce wszystkie redukcje FPT, które widziałem, są redukcjami czasu p, co oznacza, że ​​dowody twardości W [t] prawie zawsze …
1
Obliczanie maks. Zestawów wolnych od H
Na wykresie niezależny zestaw jest podzbiorem wierzchołków, który nie zawiera krawędzi jako indukowanego podsgrafu. Problem znajdowania największych niezależnych zestawów na wykresie jest fundamentalnym zagadnieniem algorytmicznym i trudnym. Rozważmy bardziej ogólne pytanie dotyczące znalezienia (wielkości) największego zestawu wolnego od H na wykresie, gdzie wolny od H oznacza, że ​​nie indukuje on …
2
Jakiś szybki algorytm problemu z ustawieniem łuku zwrotnego przy minimalnych kosztach?
Na ukierunkowanym wykresie , F ⊂ E , jeśli G ∖ F jest DAG (ukierunkowany wykres acykliczny), F nazywa się zestawem łuku zwrotnego. G=(V,E)G=(V,E)G=(V,E)F⊂EF⊂EF\subset EG∖FG∖FG\setminus FFFF Jeżeli każda krawędź jest powiązana z wagą , problem z zestawem łukowym sprzężenia zwrotnego przy minimalnym koszcie polega na znalezieniu F takiej, że W …
2
Czy problem N Queens jest trudny NP?
Problem N-królowej jest następujący: Wejście: N Wynik: umieszczenie N „królowych” na szachownicy NXN w taki sposób, że żadne dwie królowe nie leżą w tym samym rzędzie, kolumnie lub po przekątnej. Przeszukując to w Google, zauważyłem, że wiele slajdów wielu profesorów twierdzi, że jest to trudny problem NP (np. Web.mst.edu/~ercal/387/slides/NP-Hard.ppt) Jednak …
2
Minimalny True Monotone 3SAT
Interesuje mnie odmiana SAT, w której wzór CNF jest monotoniczny (żadnych zmiennych nie neguje się). Taka formuła jest oczywiście zadowalająca. Ale powiedzmy, że liczba prawdziwych zmiennych jest miarą tego, jak dobre jest nasze rozwiązanie. Mamy więc następujący problem: MINIMALNY PRAWDZIWY MONOTON 3SAT INSTANCJA: Zestaw U zmiennych, zbiór C rozłącznych klauzul …
1
Jak trudno jest zdecydować o istnieniu idealnego dopasowania czerwono-niebieskiego?
Idealnym rozwiązaniem dwukolorowego dopasowania jest decyzja, czy wykres ma koloryt w dwóch kolorach, tak aby każdy węzeł miał dokładnie jednego sąsiada tego samego koloru co on sam. Schaefer udowodnił, że problem jest NP-zupełny . Pozostaje NP-kompletny nawet dla płaskich wykresów sześciennych. Interesuje mnie wariant, w którym chcemy zdecydować, czy wykres …
2
Powszechny wgląd w hipotetyczną złożoność problemów graficznych
Natknąłem się na dwa przykłady hipotetycznej twardości niektórych problemów graficznych. Hipotetyczna twardość oznacza, że ​​obalenie niektórych przypuszczeń oznaczałoby zupełność NP odpowiedniego problemu grafowego. Na przykład, hipoteza Barnette'a stwierdza, że ​​każdy 3-połączony sześcienny dwuwymiarowy wykres jest hamiltonianem. Feder i Subi udowodnili, że obalenie przypuszczenia oznaczałoby zupełność NP problemu cyklu hamiltonowskiego na …
1
Prawdopodobieństwo wygenerowania pożądanej permutacji przez losowe zamiany
Interesuje mnie następujący problem. Jako dane wejściowe podano „permutację docelową” , a także uporządkowaną listę indeksów . Następnie, zaczynając od listy (tj. Permutacja tożsamości), przy każdym kroku zamieniamy element w z element, z niezależnym prawdopodobieństwem . Niech będzie prawdopodobieństwem, że jest generowany jako wynik.I 1 , ... , i m …
2
Twardość podtytuły Zestawu okładki
Jak trudny jest problem Ustaw okładkę, jeśli liczba elementów jest ograniczona przez jakąś funkcję (np. ), gdzie jest rozmiarem wystąpienia problemu. Formalnie,nlognlog⁡n\log nnnn Niech i gdzie i . Jak trudno jest rozwiązać następujący problemF = { S 1 , ⋯ , S n } S i ⊆ U m = …
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.