Teoretyczne informatyka

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

3
Konstruktywność w dowodzie naturalnym i złożoność geometryczna
Niedawno Ryan Willams udowodnił, że konstruktywność w naturalnym dowodzie jest nieunikniona, aby uzyskać separację klas złożoności: i . T C 0NEXPNEXP\mathsf{NEXP}TC0TC0\mathsf{TC}^{0} Konstruktywność w naturalnym dowodzie jest warunkiem, że wszystkie dowody kombinatoryczne w złożoności obwodu są spełnione i że możemy zdecydować, czy funkcja docelowa w (lub innej „twardej” klasie złożoności) ma …
3
Nietrywialny algorytm obliczania mediany okna przesuwnego
Muszę obliczyć medianę biegu: Dane wejściowe: , , wektor .nnnkkk(x1,x2,…,xn)(x1,x2,…,xn)(x_1, x_2, \dotsc, x_n) Wyjście: wektor (y1,y2,…,yn−k+1)(y1,y2,…,yn−k+1)(y_1, y_2, \dotsc, y_{n-k+1}) , gdzie yiyiy_i jest medianą (xi,xi+1,…,xi+k−1)(xi,xi+1,…,xi+k−1)(x_i, x_{i+1}, \dotsc, x_{i+k-1}) . (Brak oszustw z przybliżeniami; Chciałbym mieć dokładne rozwiązania. Elementy xixix_i są dużymi liczbami całkowitymi.) Istnieje prosty algorytm, który utrzymuje drzewo wyszukiwania …
4
Najbardziej znana deterministyczna złożoność czasu dolna granica naturalnego problemu w NP
Ta odpowiedź na główne nierozwiązane problemy w informatyce teoretycznej? pytanie stwierdza, że ​​jest otwarte, jeśli określony problem w NP wymaga czasu .Ω ( n2))Ω(n2)\Omega(n^2) Patrząc na komentarze pod odpowiedzią, zastanawiałem się: Oprócz paddingu i podobnych sztuczek, jaka jest najbardziej znana złożoność czasowa dolna granica deterministycznej maszyny RAM (lub deterministycznej maszyny …
3
Czy istnieje rozszerzenie wyrażeń regularnych, które wychwytują języki bezkontekstowe?
W wielu artykułach dotyczących gramatyk bezkontekstowych (CFG), przykłady takich gramatyk tam często dopuszczają łatwą charakterystykę generowanego języka. Na przykład: S →S→aaSbS.→zazaS.bS \to a a S b S→S.→S \to generuje ,{a2ibi|i≥0}{za2)jabja|ja≥0}\{ a^{2i} b^i | i \geq 0\} S → a a S b S →S→aSbS.→zaS.bS \to a S b S→aaSbS.→zazaS.bS \to …
1
Lemma regularności dla rzadkich wykresów
Lemma regularności Szemerediego mówi, że każdy gęsty wykres może być aproksymowany jako połączenie O ( 1 )O(1)O(1) wielu dwustronnych grafów ekspanderów. Dokładniej, istnieje podział większości wierzchołków na zestawy O ( 1 )O(1)O(1) tak że większość par zestawów tworzy dwustronne ekspandery (liczba zestawów w partycji i parametr rozszerzenia zależą od parametru …
2
Dokładna liczba porównań do obliczenia mediany
Tom III sztuki programowania komputerowego Knutha (rozdział 5, werset 3.2) zawiera poniższą tabelę zawierającą dokładną minimalną liczbę porównań wymaganych do wybrania tego najmniejszego elementu z nieposortowanego zestawu wielkości , dla wszystkich . Ta tabela, wraz z dobrze znanymi wyrażeniami typu zamkniętego i , reprezentuje większość stanu techniki w 1976 r. …
3
Złożoność „jest wykresem produkt”
To pytanie powstaje z czystej ciekawości (pojawiło się podczas myślenia o odtasowaniu łańcucha , ale nie jestem pewien, czy jest rzeczywiście powiązane), więc mam nadzieję, że jest odpowiednie. Istnieje wiele produktów graficznych i interesuje mnie którykolwiek z nich. Jaka jest złożoność ustalenia, czy wykres jest izomorficzny w stosunku do nietrywialnego …
2
Czy czasem lepiej nie publikować w ogóle?
Mam nadzieję, że nie jest to pytanie niepoprawne politycznie, ale dla doktoranta, który zwykle publikuje w CCC / ITCS / ICALP (a czasami w FOCS / STOC), może być szkodliwe (pod względem kariery zawodowej) publikowanie mniej znaczących prac w mniej prestiżowe konferencje (np. MFCS, FCT, STACS, IPL)? Czy lepiej zostawić …
2
Złożoność faktoringu w polach liczbowych
Co wiadomo na temat złożoności obliczeniowej liczb całkowitych faktoringu w ogólnych polach liczbowych? Dokładniej: Nad liczbami całkowitymi reprezentujemy liczby całkowite poprzez ich binarne rozszerzenia. Jakie są analogiczne reprezentacje liczb całkowitych w ogólnych polach liczbowych? Czy wiadomo, że pierwszeństwo nad polami liczbowymi ma postać P lub BPP? Jakie są najbardziej znane …
3
Zaokrąglanie w celu zminimalizowania sumy błędów w odległościach parami
Co wiadomo na temat złożoności następującego problemu: Biorąc pod uwagę: liczby wymierne x1&lt;x2&lt;…&lt;xnx1&lt;x2&lt;…&lt;xnx_1 < x_2 < \dotso < x_n . Wyjście: liczby całkowite y1≤y2≤…≤yny1≤y2≤…≤yny_1 \le y_2 \le \dotso \le y_n . Cel: zminimalizować ∑1≤i&lt;j≤ne(i,j),∑1≤i&lt;j≤ne(i,j),\sum_{1 \le i < j \le n} e(i,j), gdzie e(i,j)=|(yj−yi)−(xj−xi)|.e(i,j)=|(yj−yi)−(xj−xi)|.e(i,j) = | (y_j-y_i) - (x_j-x_i)|. Oznacza to, …
2
Złożoność ustalenia, czy ustalony wykres jest niewielki w stosunku do innego
W rezultacie przez Robertson Seymour wykazuje algorytm do testowania, czy stałej wykres jest minor . Mam dwa i pół pytania na ten temat:O ( n3))O(n3))O(n^3)solsolGH.H.H 1) Wygląda na to, że od tego czasu wprowadzono ulepszenia tego algorytmu. Jaki jest obecnie najbardziej znany algorytm? 2a) Co ludzie przypuszczają, że są optymalnym …
2
Dlaczego istnieje ogromna różnica między rozwiązaniami SAT?
Rozwiązują SAT są bardzo ważne w algebraicznych ataków , na przykład walksat i minisat . Jednak przy rozwiązywaniu problemów z testami porównawczymi dostępnymi tutaj istnieje ogromna różnica w wydajności między nimi - Walksat jest znacznie szybszy niż minisat dla tych problemów. Dlaczego to? Ta implementacja walksata wydaje się mieć pewne …
2
Złożoność obliczeniowa liczników indukowanych liczeniem, które dopuszczają idealne dopasowanie
Biorąc pod uwagę nieukierunkowany i nieważony wykres a jeszcze całkowita k , co jest złożoność obliczeniowa zestawów zliczania wierzchołków S ⊆ V tak, że | S | = k, a podgrupa G ograniczona do zbioru wierzchołków S dopuszcza idealne dopasowanie? Czy złożoność # P jest kompletna? Czy istnieje odniesienie do …
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.