Teoretyczne informatyka

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

1
Pozytywne uporządkowanie topologiczne, weź 2
Jest to kontynuacja ostatniego pytania Davida Eppsteina i jest motywowana tymi samymi problemami. Załóżmy, że mam wierzchołek z ciężarami na liczbach rzeczywistych na jego wierzchołkach. Początkowo wszystkie wierzchołki są nieoznaczone. Mogę zmienić zestaw zaznaczonych wierzchołków, albo (1) zaznaczając wierzchołek bez nieoznaczonych poprzedników, albo (2) odznaczając wierzchołek bez zaznaczonych następców. (Zatem …
3
Czy istnieje naturalne ograniczenie logiki VO, która przechwytuje P lub NP?
Papier Lauri Hella i José María Turull-Torres, Obliczanie zapytań z logiką wyższego rzędu , TCS 355 197–214, 2006. doi: 10.1016 / j.tcs.2006.01.009 proponuje logikę VO, logikę zmiennego rzędu. Umożliwia to kwantyfikację zamówień ponad zmiennymi. VO jest dość potężny i może wyrażać niektóre zapytania, które nie są obliczalne. (Jak wskazał Arthur …
6
Algorytmy strumienia danych „Dziel i rządź”
Jakie istnieją przydatne algorytmy, które działają na ogromnych strumieniach danych, a także ich wyniki są dość małe i można obliczyć wynik dla mieszanki dwóch strumieni, łącząc w jakiś sposób ich wyniki? Mogę wymienić kilka: Oczywiste rzeczy, takie jak suma, min, maksimum, liczba, najwyższe K itp. Przybliżone tak zwane „oparte na …
3
Derandomizacja strumieniowa
Algorytmy strumieniowe wymagają w większości przypadków randomizacji, aby zrobić coś nietrywialnego, a ze względu na ograniczenie małej przestrzeni potrzebują programów PRG, które zajmują mało miejsca. Znam dwie metody, które do tej pory były cytowane w algorytmach strumieniowych: -niezależne PRG-y, takie jak 4-mądra, niezależna rodzina używana przez Alona / Matiasa / …
1
Wydajny algorytm do niemal optymalnego kolorowania krawędzi hipergraphów
Problemy z kolorowaniem wykresów są już wystarczająco trudne dla większości ludzi . Mimo to będę musiał być trudny i zapytać o barwienie metodą hypergraph. Pytanie. Jakie są skuteczne algorytmy do znalezienia w przybliżeniu optymalnego zabarwienia krawędzi dla hipergraphów jednolitych k? Detale --- Hypergraph k-uniform to taki, w którym każda krawędź …
3
Złożoność lokalizacji w sieciach bezprzewodowych
Niech wyraźne punkty 1...n1...n1 ... n siedzieć R2R2\mathbb{R}^2 . Mówimy, że punkty iii i jjj są sąsiadami, jeśli , co oznacza, że ​​każdy punkt jest sąsiadem z punktami o indeksach w obrębie 2 , otaczających.|i−j|&lt;3(modn−2)|i−j|&lt;3(modn−2)|i-j| < 3 \pmod{n-2}222 Problemem jest: Dla każdej pary sąsiadów podajemy ich odległości par (i wiemy, …
2
Złożoność obliczeniowych zapytań w uczeniu się SQ
Wiadomo, że do uczenia się PAC istnieją naturalne klasy pojęć (np. Podzbiory list decyzji), w których występują wielomianowe luki między złożonością próby potrzebną do teoretycznego uczenia się informacji przez uczonego bez ograniczeń obliczeniowych a złożonością próby potrzebną przez wielomian uczący się czasu. (patrz np. http://portal.acm.org/citation.cfm?id=267489&amp;dl=GUIDE lub http://portal.acm.org/citation.cfm?id=301437 ) Wyniki te …
2
Proste zrównoważone drzewa z concat O (1)?
W czysto funkcjonalnych najgorszych przypadkach sortowanych list o stałym czasie, Brodal i in. prezentuj czysto funkcjonalne zrównoważone drzewa z konkatenatem O (1) i wstawiaj, usuwaj i znajduj O (lg n). Struktura danych jest nieco skomplikowana. Czy istnieje prostsze zrównoważone drzewo wyszukiwania z konkatenacją O (1), funkcjonalne czy nie?
1
Problem techniczny z dowodem twierdzenia PCP
Czytam stąd dowód i natknąłem się na problem techniczny (ale kluczowy). Wiem, że jest to dość specyficzne i kontekst jest problematyczny, ale sam nie mogłem tego pojąć. Na stronach 51 i 55, po przedstawieniu „standardowych” weryfikatorów, przechodzą do modyfikacji weryfikatorów w celu sprawdzenia podzielonych zadań. W pierwszym przypadku (s. 51) …
4
Jak być bardziej „nastawionym na teorię”?
Z góry przepraszamy za to miękkie pytanie, które nie ma zamkniętej, poprawnej odpowiedzi. To chyba najlepsze forum do zadawania moich pytań. Jestem studentem trzeciego roku w grupie teoretycznej 15 najlepszych szkół w USA. Jak dotąd radziłem sobie całkiem nieźle. Mam do tej pory pierwszą pracę teoretyczną i pierwszą pracę praktyczną. …
1
Przykład logarytmicznej długości świadka jest łatwiejszy do zweryfikowania niż znalezienia
Łatwe spostrzeżenie, że, jeżeli problem jest rozstrzygalne przez wielomian czasu niedeterministycznych programu przy O ( log n ) niedeterministycznych bitów (czyli wszystkie świadków logarytmiczna długości), a następnie ∈ P .ZAAAO(logn)O(log⁡n)O(\log n)A∈PA∈PA \in \mathsf{P} Jeśli ktoś zadaje pytanie: „Czy łatwiej jest zweryfikować świadka niż go znaleźć?” dla takich problemów, i uważa …
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.