Teoretyczne informatyka

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

2
Twierdzenie o hierarchii wielkości obwodu
Myślę, że twierdzenie o hierarchii wielkości dla złożoności obwodów może być dużym przełomem w tej dziedzinie. Czy to ciekawe podejście do separacji klasowej? Motywem tego pytania jest to, że musimy powiedzieć istnieje pewna funkcja, której nie można obliczyć na podstawie obwodów wielkości f(n)f(n)f(n) i można ją obliczyć na podstawie obwodu …
3
Luka integralności i współczynnik aproksymacji
Gdy weźmiemy pod uwagę algorytm aproksymacji dla problemu minimalizacji, luka integralności formuły IP dla tego problemu daje dolną granicę współczynnika aproksymacji dla pewnej klasy algorytmów (takich jak algorytm zaokrąglania lub pierwotny podwójny). W rzeczywistości istnieje wiele problemów, których najlepszy współczynnik aproksymacji odpowiada luce integralności. Niektóre algorytmy mogą mieć lepszy współczynnik …
3
Obliczanie sumy rzadkich wielomianów podniesionych do kwadratu w czasie O (n log n)?
Załóżmy, że mamy wielomiany stopnia co najwyżej , , tak że całkowita liczba niezerowych współczynników wynosi (tzn. Wielomiany są rzadkie). Interesuje mnie wydajny algorytm obliczania wielomianu:p1,...,pmp1,...,pmp_1,...,p_mn > m nnnnn>mn>mn>mnnn ∑ipi(x)2∑ipi(x)2\sum_i p_i(x)^2 Ponieważ ten wielomian ma stopień co najwyżej 2n2n2n , zarówno wielkość wejściowa, jak i wyjściowa wynosi O(n)O(n)O(n) . W …
2
Czy istnieje twierdzenie Hierarchia czasu dla PH?
Czy to prawda, że ​​w hierarchii wielomianowej występują problemy, które można rozwiązać w czasie O(nk)O(nk)O(n^k) (przez naprzemienną maszynę Turinga na pewnym poziomie hierarchii wielomianowej), których nie można rozwiązać w O(nk−1)O(nk−1)O(n^{k-1}) na żadnym poziomie hierarchia wielomianowa? Innymi słowy - czy istnieje twierdzenie o hierarchii czasu dla hierarchii wielomianowej, tak jak ma …
1
Poczwórna struktura danych (Delaunay / Voronoi)
2 pytania do geometrii obliczeniowej lub algebraistów: Właśnie zaczynam nurkować w geometrii obliczeniowej i uwielbiam ją =) Próbuję przeczytać słynny artykuł Guibasa i Stolfiego zatytułowany „Prymitywy do manipulowania ogólnymi poddziałami i obliczaniem diagramów Voronoi” w celu zaimplementowania algorytmu triangulacji Delaunaya. Kusi mnie, aby pominąć wszystkie teoretyczne rzeczy i po prostu …
2
Podpisywanie niejawne a jawne
Ta strona to potwierdza wiele języków nie używa ukrytego podtytułu (równoważność strukturalna), preferując jawne / zadeklarowane podtypy (równoważność deklaracji) Najczęściej używałem języków programowania, które używają jawnego podtytułu . Jakie są zalety ukrytego podtypu, jak opisano w uwagach powyżej.
3
Uogólnienia metody Brzozowskiego pochodnych wyrażeń regularnych do gramatyki?
Metoda pochodnych Brzozowskiego jest bardzo ładną techniką do budowania deterministycznych automatów z wyrażeń regularnych w ładnie algebraiczny sposób. Opracowałem kilka uroczych uogólnień tej techniki do obsługi niektórych większych klas gramatycznych, ale algorytmy są na tyle proste, że wydaje się całkiem możliwe, że zostały wcześniej odkryte. Ale wydaje się, że odniesienia …
4
Zastosowania teorii złożoności
Teoria złożoności wydaje się uchwycić coś fundamentalnego w strukturze wszechświata, ponieważ formalizuje intuicyjne przekonanie, że niektóre problemy są trudniejsze niż inne. Scott Aaronson przewidział : „Założenie o twardości NP będzie w końcu postrzegane jako analogiczne do drugiej zasady termodynamiki lub niemożności sygnalizacji nadświetlnej”. Tak zwane „trudne problemy” są podstawą współczesnej …
5
Prosty i praktyczny algorytm deterministyczny, skomplikowany czas działania
Bardzo często, jeśli czas działania algorytmu jest skomplikowanym wyrażeniem, sam algorytm jest również skomplikowany i niepraktyczny. Każdy z pierwiastek sześcienny i czynników w czasie biegu asymptotycznej tendencję, aby dodać złożoności algorytmu, a także ukryte czynniki stałe do czasu pracy.loglognlog⁡log⁡n\log \log n Czy mamy uderzające przykłady, w których zawodzi ta praktyczna …
2
Wymagania dotyczące pamięci dla wyboru mediany (algorytmy dwuprzebiegowe)
W klasycznej pracy Munro i Paterson badają problem ilości pamięci potrzebnej algorytmowi do znalezienia mediany w losowo posortowanej tablicy. W szczególności koncentrują się na następującym modelu: wejście jest odczytywane od lewej do prawej kilka razy P. Pokazano, że komórki pamięci są wystarczające, ale odpowiadająca dolna granica jest znana tylko dla …
1
Techniki wykazywania nieprzekraczalności w logice i innych formalnych systemach dowodowych
W systemach dowodowych dla klasycznej logiki zdań, jeśli chce się wykazać, że pewna formuła nie jest pochodna, po prostu pokazuje, że można uzyskać (chociaż z pewnością możliwe są inne techniki). Brak możliwości wyprowadzenia wynika zasadniczo z prawidłowości i kompletności systemu dowodowego.ψψ\psi¬ ψ¬ψ\neg\psi Niestety w przypadku nieklasycznej logiki i bardziej egzotycznych …
18 lo.logic 
1
Czy dominujący problem z zestawem jest ograniczony do płaskich dwustronnych grafów o maksymalnym stopniu NP-3?
Czy ktoś wie o wyniku NP-kompletności dla problemu ZESTAW DOMINUJĄCY na wykresach, ograniczonego do klasy płaskich dwustronnych grafów o maksymalnym stopniu 3? Wiem, że jest NP-kompletny dla klasy grafów płaskich o maksymalnym stopniu 3 (patrz książka Gareya i Johnsona), a także dla grafów dwustronnych o maksymalnym stopniu 3 (patrz M. …
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.