Pytania otagowane jako exp-time-algorithms

4
Algorytmy aproksymacyjne dla metrycznego TSP
Wiadomo, że metryczny TSP może być przybliżony w granicach i nie może być przybliżony lepiej niż 1231.51.51.5 w czasie wielomianowym. Czy coś wiadomo na temat znajdowania rozwiązań aproksymacyjnych w czasie wykładniczym (na przykład mniej niż2nkroków z tylko przestrzenią wielomianową)? Np. W jakim czasie i przestrzeni możemy znaleźć trasę, której odległość …
2
Ile różnych kolorów jest potrzebnych, aby ograniczyć możliwości wyboru wykresu?
Wykres jest kkk wyboru (znany również jako kkk -list-colorable ), jeśli dla każdej funkcji fff która odwzorowuje wierzchołki na zestawy kkk kolorów, istnieje przypisanie kolorów ccc tak że dla wszystkich wierzchołków vvv , c(v)∈f(v)c(v)∈f(v)c(v)\in f(v) i takie, że dla wszystkich krawędzi vwvwvw , c(v)≠c(w)c(v)≠c(w)c(v)\ne c(w) . Załóżmy teraz, że wykres …
2
Czy jakieś algorytmy kwantowe poprawiają klasyczne SAT?
Klasyczne algorytmy mogą rozwiązać 3-SAT w czasie (losowo) lub (deterministycznie). (Odnośnik: najlepsze górne granice na SAT )1,3303 n1,3071n1.3071n1.3071^n1,3303n1.3303n1.3303^n Dla porównania, użycie algorytmu Grovera na komputerze kwantowym i zapewniło rozwiązanie w losowaniu losowym . (Może to nadal wymagać pewnej wiedzy o tym, ile rozwiązań może istnieć, ale nie jestem pewien, jak …
3
Dokładne rozwiązywanie superstrun
Co wiadomo o dokładnej złożoności najkrótszego problemu superstrun? Czy można to rozwiązać szybciej niż O∗(2n)O∗(2n)O^*(2^n) ? Czy znane są algorytmy, które rozwiązują najkrótszy superstrun bez redukcji do TSP? UPD: O∗(⋅)O∗(⋅)O^*(\cdot) tłumi czynniki wielomianowe. Najkrótszy problem superstrun to problem, którego odpowiedzią jest najkrótszy ciąg, który zawiera każdy ciąg z danego zestawu …
1
Problem decydowania, czy monotoniczny CNF implikuje monotoniczny DNF
Rozważ następujący problem decyzyjny Wejście : monotoniczny CNF ΦΦ\Phi i monotonowy DNFΨΨ\Psi . Pytanie : Czy Φ→ΨΦ→Ψ\Phi \to \Psi jest tautologią? Zdecydowanie możesz rozwiązać ten problem w czasie O(2n⋅poly(l))O(2n⋅poly(l))O(2^n \cdot \mathrm{poly}(l)) , gdzie nnn jest liczbą zmiennych w Φ→ΨΦ→Ψ\Phi \to \Psi a lll jest długością wejściową. Z drugiej strony ten …
3
Przykłady problemów, w których algorytmy wykładnicze działają szybciej niż algorytmy wielomianowe dla praktycznych rozmiarów?
Czy znasz jakieś problemy (najlepiej przynajmniej nieco dobrze znane), w których dla praktycznego rozmiaru problemu algorytm wykładniczy działa znacznie szybciej niż najbardziej znany odpowiednik czasu wielomianowego. Załóżmy na przykład, że problem ma praktyczny rozmiar * i istnieją dwa znane algorytmy: jeden to a drugi to dla pewnej stałej . Oczywiście …
1
Dokładne algorytmy dla niewypukłego programowania kwadratowego
To pytanie dotyczy kwadratowych problemów programistycznych z ograniczeniami pudełkowymi (box-QP), tj. Problemów optymalizacyjnych formularza minimalizuj zastrzeżeniem x ∈ [ 0 , 1 ] n .fa( x ) = xT.A x + cT.xf(x)=xTAx+cTxf(\mathbf{x}) = \mathbf{x}^T A \mathbf{x} + \mathbf{c}^T \mathbf{x}x ∈[0,1 ]nx∈[0,1]n\mathbf{x} \in [0,1]^n Gdyby było pozytywnie półokreślone, wtedy wszystko byłoby …
2
?
Czy to możliwe, że ? Czy są interesujące konsekwencje takiego ograniczenia? Czy byłoby to sprzeczne z hipotezą o wykładniczym czasie?S.A T.¯¯¯¯¯¯¯¯¯¯∈ N.T.jaM.mi( exp( n0,9) )S.ZAT.¯∈N.T.jaM.mi(exp⁡(n0,9))\overline{SAT} \in NTIME(\exp(n^{0.9}))
1
Model obliczeniowy w SETH
Impagliazzo, Paturi i Calabro, Impagliazzo, Paturi wprowadzili hipotezę czasu wykładniczego (ETH) i hipotezę silnie wykładniczego czasu (SETH). Z grubsza, SETH mówi, że nie ma algorytmu, który rozwiązuje SAT w czasie . 1,99n1,99n1.99^n Zastanawiałem się, co to znaczy złamać SETH. Zdecydowanie musimy znaleźć algorytm, który rozwiązuje SAT w mniej niż krokach, …
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 = …
2
Dokładne algorytmy czasu wykładniczego dla programów 0-1 z danymi nieujemnymi
Czy są znane algorytmy dla następującego problemu, które pokonały naiwny algorytm? Dane wejściowe: matryca AAA i wektory b,cb,cb,c, gdzie wszystkie wpisy z pozycji A,b,cA,b,cA,b,c są liczbami całkowitymi nieujemnymi. Wyjście: optymalne rozwiązanie x∗x∗x^* do max{cTx:Ax≤b,x∈{0,1}n}max{cTx:Ax≤b,x∈{0,1}n}\max \{ c^T x : Ax \le b, x \in \{ 0,1\}^n \}. To pytanie jest udoskonaloną …
2
Złożoność czasowa algorytmu Held-Karp dla TSP
Kiedy przejrzałem „ Dynamiczne podejście programistyczne do problemów z sekwencjonowaniem ” autorstwa Michaela Helda i Richarda M. Karpa, wpadłem na następujące pytanie: dlaczego złożoność ich algorytmu dla TSP jest (s. 199), mam na myśli skąd biorą współczynnik ? Jeśli dobrze zrozumiałem, k-1 oznacza liczbę dodatków dla każdego podzbioru miast. To …
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.