Pytania otagowane jako ds.algorithms

Pytania dotyczące dobrze zdefiniowanych instrukcji wykonania zadania oraz odpowiedniej analizy pod względem czasu / pamięci / itp.

5
Pozytywne uporządkowanie topologiczne
Załóżmy, że mam ukierunkowany wykres acykliczny z wagami liczb rzeczywistych na jego wierzchołkach. Chcę znaleźć uporządkowanie topologiczne DAG, w którym dla każdego prefiksu uporządkowania topologicznego suma wag jest nieujemna. Lub jeśli wolisz terminologię teoretyczną, mam ważoną częściową kolejność i chcę liniowego rozszerzenia, aby każdy prefiks miał nieujemną wagę. Co wiadomo …
8
Nekrologi martwych przypuszczeń
Szukam domysłów na temat algorytmów i złożoności, które przez pewien czas były postrzegane przez wielu jako wiarygodne, ale później zostały one obalone lub przynajmniej niewiary, z powodu narastających kontr-dowodów. Oto dwa przykłady: Hipoteza o losowej wyroczni: relacje między klasami złożoności, które dotyczą prawie wszystkich relatywizowanych światów, dotyczą również przypadku nie …
8
Znaczenie luki w integralności
Zawsze miałem problem ze zrozumieniem znaczenia luki integralności (IG) i ją ograniczam. IG jest stosunkiem (jakości) optymalnej liczby całkowitej do (jakości) optymalnego rzeczywistego rozwiązania złagodzenia problemu. Rozważmy przykrycie wierzchołków (VC) jako przykład. VC można określić jako znalezienie optymalnego rozwiązania liczb całkowitych następującego zestawu równań liniowych: Mamy zero / jednego o …
8
Najlepsze górne granice na SAT
W innym wątku Joe Fitzsimons zapytał o „najlepsze obecne dolne granice 3SAT”. Chciałbym pójść w drugą stronę: jakie są najlepsze obecne górne granice 3SAT? Innymi słowy, jaka jest złożoność czasowa najbardziej wydajnego solvera SAT? W szczególności, czy można sobie wyobrazić algorytm subwykładniczy (a jednak super-wielomianowy) dla SAT?
3
Konsekwencje quasi-wielomianowego algorytmu czasowego dla problemu izomorfizmu grafowego
Problemem wykres Izomorfizm (Gl) jest prawdopodobnie najbardziej znanym kandydatem na NP pośredniego problemu. Najbardziej znanym algorytmem jest algorytm subwykładniczy z czasem działania . Wiadomo, że GI nie jest -kompletny, chyba że hierarchia wielomianowa się załamie.2O(nlogn√)2O(nlog⁡n)2^{O(\sqrt{n \log n})}NPNP\mathsf{NP} Jakie byłyby teoretyczne konsekwencje złożoności quasi-wielomianowego algorytmu czasowego dla problemu grafowego izomorfizmu? Czy …
6
Złożoność znalezienia składowej macierzy
Moje pytanie jest proste: Jaki jest najgorszy czas z najbardziej znanych algorytm działa dla wyliczania eigendecomposition danego matrycy?n×nn×nn \times n Czy skład eigend redukuje się do mnożenia macierzy, czy w najgorszym przypadku są najlepiej znanymi algorytmami (przez SVD )?O(n3)O(n3)O(n^3) Proszę zauważyć, że proszę o analizę najgorszego przypadku (tylko w kategoriach …
1
Algorytm sortowania, dzięki któremu każdy element jest porównywany razy i nie zależy od sieci sortującej
Czy istnieją znane algorytmy porównywania, które nie ograniczają się do sortowania sieci, tak że każdy element jest porównywany razy?O ( logn )O(log⁡n)O(\log n) O ile mi wiadomo, jedynym sposobem sortowania za pomocą porównania na każdym elemencie jest zbudowanie sieci sortującej AKS dla danych wejściowych i uruchomienie danych wejściowych w sieci …
4
Przykłady, w których wyjątkowość rozwiązania ułatwia znalezienie
Klasa złożoności składa się z tych N P -Problemy że może być określana przez wielomian czasu niedeterministycznych maszynie Turinga, który ma co najwyżej jedną ścieżkę akceptacji obliczeniowej. Oznacza to, że rozwiązanie, jeśli w ogóle, jest wyjątkowe w tym sensie. Uważa się wysoce nieprawdopodobne, że wszystkie U P -Problemy są P …
2
Trudne problemy z sumą pierwiastków kwadratowych?
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 w problemach związanych z najkrótszymi ścieżkami euklidesowymi, i stanowi …
6
Złożoność algorytmu simpleks
Jaka jest górna granica algorytmu simpleks dla znalezienia rozwiązania dla programu liniowego? Jak mam znaleźć dowód na taką sprawę? Wydaje się, że najgorszym przypadkiem jest konieczność odwiedzenia każdego wierzchołka, czyli . Jednak w praktyce algorytm simpleks będzie działał znacznie szybciej niż w przypadku bardziej standardowych problemów.O ( 2n)O(2n)O(2^n) Jak mogę …
4
Czy istnieje funkcja skrótu dla zbioru liczb całkowitych (tj. Wielu), która ma dobre gwarancje teoretyczne?
Ciekawe, czy istnieje sposób przechowywania skrótu zbioru liczb całkowitych, który ma następujące właściwości, najlepiej: Wykorzystuje spację O (1) Można go zaktualizować, aby odzwierciedlał wstawianie lub usuwanie w czasie O (1) Dwie identyczne kolekcje (tj. Kolekcje, które mają te same elementy o tych samych wielokrotnościach) zawsze powinny mieć skrót do tej …
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.