Pytania otagowane jako parameterized-complexity

Badanie złożoności obliczeniowej problemów w odniesieniu do więcej niż jednego parametru.

1
Delikatne wprowadzenie do algorytmicznych aspektów głębokości drzewa
Szerokość i szerokość ścieżki są popularnymi parametrami, mierzącymi odpowiednio bliskość wykresu do drzewa lub ścieżki. Rzeczywiście wydaje się, że szerokość jest tak popularna, że ​​pojawia się w wielu artykułach, książkach i notatkach z wykładów, które dają (nawet bardzo delikatne) wprowadzenie do algorytmicznych aspektów szerokości (patrz np. Książka Downey & Fellows). …
1
Złożoność obwodu monotonicznego funkcji obliczeniowych na rzadkich wejściach
Wagaciągu binarnego to liczba jedynek w ciągu. Co się stanie, jeśli będziemy zainteresowani obliczeniem funkcji monotonicznej na wejściach z kilkoma?x ∈ { 0 , 1 } n| x ||x||x|x ∈ { 0 , 1 }nx∈{0,1}nx\in\{0,1\}^n Wiemy, że podjęcie decyzji, czy wykres ma klasę jest trudne dla obwodów monotonicznych (patrz między …
1
Jakieś wyniki na binarnym CSP typu boolean wykraczają poza ustalalność parametrów prawie problemu 2SAT?
Niech będzie formułą 2CNF, a k nieujemną liczbą całkowitą. Jest udowodnione w tym artykule , że problem z podjęciem decyzji, czy można usunąć co najwyżej k klauzul aby φ satisfable określony jest parametr tractable, gdzie k jest parametrem. Moje pytanie brzmi: czy są jakieś prace, które uogólniają ten wynik na …
1
Czy wykresy „rodzaju zewnętrznego” mają stałą szerokość grzbietu?
Niech i przez zestaw wszystkich wykresów, które mogą być osadzone na powierzchni rodzaju tak, aby wszystkie wierzchołki znajdowały się na zewnętrznej powierzchni . Na przykład jest zbiorem zewnętrznych wykresów płaskich. Czy szerokość wykresów w być ograniczona przez jakąś funkcję ?G k k G 0 G k kk∈Nk∈Nk\in\mathbb{N}GkGkG_kkkkG0G0G_0GkGkG_kkkk Drugi kierunek oczywiście …
1
Sparametryzowana złożoność włączenia zwykłych języków
Interesuje mnie klasyczny problem REGULARNE WŁĄCZENIE JĘZYKA. Biorąc pod uwagę wyrażenie regularne , oznaczamy przez L ( E ) powiązany z nim język regularny. (Wyrażenia regularne są na stałej alfabetu Ď z unii operacji, Kleene-gwiazdkowe i konkatenacji).miEEL ( E)L(E)L(E)ΣΣ\Sigma Dane wejściowe: dwa wyrażenia regularne i E 2 Pytanie: Czy to …
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 …
2
Które problemy z grafem są trudne dla na wykresach skierowanych (/ ważonych), ale FPT na wykresach niekierowanych (/ nieważonych)?
Po równoważnych pytaniach dotyczących kompletności NP (patrz pytanie wagi i pytanie kierowane ) zastanawiałem się, w jaki sposób atrybuty te wpływają na sparametryzowane problemy. Które problemy z twardym grafem są trudne dla na grafach ukierunkowanych, ale stały parametr można traktować na grafach bezkierunkowych?NPNPNPW[1]W[1]W[1] Które problemy z twardym grafem są trudne …
1
Czy sparametryzowana złożoność będzie przyszłością teorii złożoności?
Jestem naukowcem, który pracuje w teorii algorytmów i złożoności, do pewnego stopnia używam sparametryzowanej złożoności. Wydaje mi się, że badacze o sparametryzowanej złożoności są bardzo aktywni (nie mam na myśli, że inni nie) pod względem liczby prac badawczych. Widziałem, że badacze ze złożoności komunikacyjnej, złożoności arytmetycznej itp. Również w większym …
1
Sparametryzowana złożoność liczenia rowerów
W poprzednim pytaniu Sparametryzowany algorytm znajdowania biklików zapytałem, czy istnieją szybkie sparametryzowane algorytmy do znalezieniak×kk×kk\times k-biclique in an nnn wykres wierzchołków i dowiedziałem się, że był otwarty, jeśli jest FPT wrt kkk. To samo odnosi się do liczeniak×kk×kk\times k-bikiety, czy wiadomo, że to #W\[1\]W\[1\]W\[1\]-hard wrt kkk (lub jakieś inne pojęcie …
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.