Analiza złożoności czasu dla algorytmu UST-CONN Reingolda

Jaka jest dokładna złożoność czasowa niekierowanego algorytmu przestrzeni logów st-connectivity autorstwa Omer Reingold?

cc.complexity-theory randomness

— Suresh Venkat
źródło

Proszę być bardziej konkretnym. Opisz swoje pytanie wystarczająco szczegółowo i przytocz odpowiednie odniesienia.

— MS Dousti,

Myślę, że pytanie jest dość jednoznaczne: doi.acm.org/10.1145/1391289.1391291 to artykuł.

— András Salamon,

Pytanie jest dość jednoznaczne dla tych, którzy pracują w tej okolicy, ale prawdopodobnie dobrym pomysłem jest poproszenie plakatów o więcej informacji, aby szersza publiczność mogła zrozumieć pytanie.

— Robin Kothari,

Wydaje się, że złożoność czasowa algorytmu Reingolda nie jest rozpatrywana ani w pracy Reingolda, ani w podręczniku Arora-Baraka. Wydawałoby się również, że analiza jest dość nużąca, ponieważ złożoność czasowa zależy od dokładnego wykresu ekspandera zastosowanego w konstrukcji oraz od niektórych stałych, które są wybierane jako „wystarczająco duże”.

Aby uzyskać ogólne pojęcie o złożoności czasowej, należy zauważyć, że algorytm Reingolda, biorąc pod uwagę wykres , przekształca go (domyślnie) w wykres ekspandera i przemierza każdy krok długości . The -notation ukrywa niektóre dość duże stałe tutaj. Wykres ma stałą stopień jakiegoś wystarczająco dużej , co oznacza, że istnieje takie spacery jakiegoś dość dużą stałą $G$ $G'$ $l = O(\log n)$ $O$ $G'$ $d = 2^b$ $b$ $d^l = O(n^c)$ . Przeglądając niektóre notatki z wykładu na ten temat, wydaje się, że . $c$ $c \ge 10^9b$

— Janne H. Korhonen
źródło

następnym razem nie oznaczaj swojej odpowiedzi jako wiki społeczności. W przeciwnym razie nie otrzymasz kredytu za odpowiedź!

— Ryan Williams,

Myślałem, że ktoś może chcieć sprecyzować moją analizę, i nie zdawałem sobie sprawy, że nie zyskujesz reputacji na wiki społeczności. No cóż.

— Janne H. Korhonen,