Teoretyczne informatyka

Pytania i odpowiedzi dotyczące teoretycznych informatyków i badaczy w pokrewnych dziedzinach

6
Złożoność algorytmu tasowania Fishera-Yatesa
To pytanie dotyczy algorytmu Fishera-Yatesa służącego do zwracania losowego losowania danej tablicy. The Wikipedii mówi, że jego złożoność wynosi O (n), ale myślę, że jest to O (n log n). W każdej iteracji i losowa liczba całkowita jest wybierana między 1 a i. Po prostu zapisywanie liczby całkowitej w pamięci …
1
vs
W naszej ostatniej pracy rozwiązujemy problem obliczeniowy, który powstał w kontekście kombinatorycznym, przy założeniu, że , gdzie to -wersja . Jedyny artykuł na temat , który znaleźliśmy, to artykuł Beigel-Buhrman-Fortnow 1998 , cytowany w Zoo Complexity . Rozumiemy, że możemy wziąć wersje parzystości problemy (zobacz to pytanie ), ale być …
3
Izomorfizm podsgrafu z drzewem
Jeśli mamy duży (skierowany) wykres i mniejsze ukorzenione drzewo H , jaka jest najbardziej znana złożoność znajdowania podgraphów G izomorficznych względem H ? Zdaję sobie sprawę z wyników dla izomorfizmu poddrzewa, w którym zarówno G, jak i H są drzewami, a także gdzie G jest płaski lub ma ograniczoną szerokość …
2
Automaty Büchi ze strategią akceptacji
Problem Niech = ⟨ Ď , P , Q 0 , F , Δ ⟩ jest automatem Biichi rozpoznawania języka . Zakładamy, że ma strategię odbioru w następującym sensie: jest funkcja , które mogą być używane do tras pilotażowych . Formalizujemy to, spełniając następujące warunki:A=⟨Σ,Q,q0,F,Δ⟩A=⟨Σ,Q,q0,F,Δ⟩A=\langle \Sigma, Q, q_0,F,\Delta\rangleL⊆ΣωL⊆ΣωL\subseteq\Sigma^\omegaAAAσ:Σ∗→Qσ:Σ∗→Q\sigma:\Sigma^*\to QAAA σ(ϵ)=q0σ(ϵ)=q0\sigma(\epsilon)=q_0 …
5
Jaka jest klasa złożoności podprogramów kwantowych przyjmujących dowolne stany kwantowe jako dane wejściowe?
Klasa złożoności BQP odpowiada podprogramom kwantowym w czasie wielomianowym, przyjmującym klasyczne dane wejściowe i wyrzucającym probabilistyczny sygnał klasyczny. Porada kwantowa modyfikuje to, aby uwzględnić kopie niektórych z góry określonych stanów porady kwantowej, ale jak zwykle z klasycznymi danymi wejściowymi. Jaka jest klasa złożoności podprogramów kwantowych czasu wielomianowego przyjmujących dowolne stany …
2
Jaki jest najszybszy algorytm do obliczania rangi macierzy prostokątnej?
Biorąc pod uwagę macierz m×nm×nm \times n (przy założeniu, że m≥nm≥nm \ge n ), jaki jest najszybszy algorytm obliczający swoją pozycję i podstawę kolumn? Wiem, że można to rozwiązać za pomocą liniowego przecięcia macierzy, co implikuje algorytm deterministyczny czasowy i algorytm randomizowany czasowo O ( m n ω - 1 …
2
Analogi kwantowe klas złożoności SPACE
Często rozważamy klasy złożoności, w których jesteśmy ograniczeni ilością miejsca, które może wykorzystać nasza maszyna Turinga, na przykład: DSPACE(f(n))DSPACE(f(n))\textbf{DSPACE}(f(n)) lub NSPACE(f(n))NSPACE(f(n))\textbf{NSPACE}(f(n)) . Wydaje się, że we wczesnej teorii złożoności odniesiono duży sukces z tymi klasami, takimi jak twierdzenie o hierarchii przestrzeni i tworzenie ważnych klas, takich jak LL\textbf{L} i PSPACEPSPACE\textbf{PSPACE} …
3
Jak można motywować relacyjną parametryczność?
Czy istnieje jakiś naturalny sposób na zrozumienie istoty semantyki relacyjnej polimorfizmu parametrycznego? Właśnie zacząłem czytać o pojęciu parametryczności relacyjnej, a la John Reynolds „Typy, abstrakcja i polimorfizm parametryczny” i mam problem ze zrozumieniem, w jaki sposób motywowana jest semantyka relacyjna. Zestaw semantyki ma dla mnie idealny sens i zdaję sobie …
3
Sprawdzenie wzorów dwa kwantyfikatorów (
Solwery SAT dają potężny sposób na sprawdzenie poprawności formuły logicznej za pomocą jednego kwantyfikatora. Na przykład, aby sprawdzić poprawność , możemy użyć solwera SAT, aby ustalić, czy φ ( x ) jest zadowalające. Aby sprawdzić ważność ∀ x . φ ( x ) , możemy użyć solwera SAT do ustalenia, …
3
Postęp w ogólnym problemie z wysokością gwiazdy?
(Uogólniona) wysokość gwiazdy w języku jest minimalnym zagnieżdżeniem gwiazd Kleene wymaganym do przedstawienia języka za pomocą rozszerzonego wyrażenia regularnego. Przypomnijmy, że rozszerzonym wyrażeniem regularnym ponad skończonych alfabet spełnia następujące:ZAAA (1) i są rozszerzone wyrażenia regularne dla wszystkich A ∈∅ , 1∅,1\emptyset, 1zaaaa ∈ Aa∈Aa\in A (2) Dla wszystkich rozszerzonych wyrażeń …
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.